# Asymptotic Notation

### Asymptotic Notation Video Explanation:

The following 3 asymptotic notations are mostly used to represent time complexity of algorithms.

**Big-Oh Notation**

Big-Oh notation is a convenient way to express the worst-case scenario of a given algorithm. This is the most used notation any programmer will come across.

Mathematically, we say that

f(n) = O(g(n)) when there exist constants c > 0 and n_{0} > 0 such that *f(n) ≤ c* g(n)*, for all n ≥ n_{0}

Big-Oh Notation gives us an upper bound on running time.** **

**Rules**

- If we have a polynomial as f(n), you can ignore the lower-order terms i.e. the terms having lower degrees of n and select the highest power.

Eg: f(n) = n + n^{2 }+ n^{3}= O(n^{3}) - We drop the constants.

Eg: f(n) = 2n^{2}= O(n^{2})

**Big-Oh Notation Examples:**

- 1 = O(n)
- 2n
^{2}+ 3n + 1 = O(n^{2}) - nlog(n) = O(n
^{2}) - 2
^{n+10}= O(2^{n})

Complexity of an algorithm is said to be linear if its running time is O(n)

Eg: Linear Search in an array

Complexity of an algorithm is said to be logarithmic if its running time is O(log(n))

Eg: Binary Search in an array

Complexity of an algorithm is said to be quadratic if its running time is O(n^{2})

Eg: Selection sort, Insertion Sort

**Big – Omega Notation
**Omega Notation gives us an asymptotic lower bound on the running time of an algorithm.

We say that f(n) = Ω(g(n))

when there exist constant c that *f(n) ≥ c*g(n)* for for all sufficiently large n.

**Big – Omega Notation Examples:**

- n = Ω(1)
- n
^{2}= Ω(n) - n
^{2}= Ω(n log(n))

The time complexity of Insertion Sort can be written as Ω(n), but it is not very useful information about insertion sort, as already mentioned.

**Theta Notation**

Theta Notation gives us the average running time for our algorithm.

We say that f(n) = Θ(g(n)) if and only f(n) = O(g(n)) and f(n) = Ω(g(n)).

Mathematically, we say that

f(n) = Θ(g(n)) when there exist constants c1 and c2 such that *c1*g(n)<= f(n)<= c2*g(n)* for all n ≥ n_{0}

Theta is known as asymptotic tight bound which shows actual behavior of the algorithm.

**Theta Notation Examples:**

- 2 n = Θ(n)
- n
^{2}+ 2 n + 1 = Θ( n^{2})

**NOTE: Theta is not defined if the worst case and best case time complexity of a function are different.**