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 iBig-Oh Notations 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 NotationOmega 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 NotationTheta 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.