# Asymptotic Notation

By | January 12, 2016

# 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 n0 > 0 such that f(n) ≤ c* g(n), for all n ≥ n0

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

Rules

1. 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 + n2 + n3 = O(n3)
2. We drop the constants.
Eg: f(n) = 2n2 = O(n2)

Big-Oh Notation Examples:

• 1 = O(n)
• 2n2 + 3n + 1 = O(n2)
• nlog(n) = O(n2)
• 2n+10 = O(2n)

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(n2)
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)
• n2 = Ω(n)
• n2 = Ω(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 ≥ n0

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

Theta Notation Examples:

• 2 n = Θ(n)
• n2 + 2 n + 1 = Θ( n2)

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