Time Complexity Ordering

Order of time complexity :

Questions based on arrangement of time complexity can be solved by dividing problem into polynomial and exponential class.

Exponential class has always higher order compared to polynomial

Linear class has least order compared to both polynomial and exponential class.

Example

1)  arrange following in increasing order :

     

     n!,   2^(n),    n^(logn)

Answer : n^(logn) <  2^(n)  <  n!

2) 2^(n) ,  n^(3/2) , nlogn,  n^(logn)

Answer:     nlogn (linear)  <  n^(3/2) (polynomial)  <  n^(logn) (polynomial of power logn)  < 2^(n) (exponential)

3) Ascending order :

O(1) < O(logN)  <  O(NlogN)  < O(N^(3/2))  < O(N^(2))  <  O(N^(2)logN)

Dominance rule :

c (constant) < logn  <  n  <  nlogn  <  n^(2)  <  n^(3)  < .......<  2^(n) <  3 ^(n)  < ......<  n^(n)  <  n^n^n.

Feel free to  ask any questions, i will try to update solution here. for solutions visit my blog regularly.