Search code examples
algorithmtime-complexitybig-ocomputer-science

Ordering Big O-complexity function according to complexity


I'm trying to order the following functions in terms of Big O complexity from low complexity to high complexity:

100n, 2^n , 2^log^3 n , log^n, n^100 , log log n, 2^n^2, n^log n , n^√n , 2^2^n

Here, all logs are base 2.

I have ordered them following way. Is this order of Big O-complexity correct?

log n 
100n 
log log n
2^n
n^100
n^√n
n^log n
2^log^3 n
2^n^2
2^2^n

Solution

  • Correct order is:

    log log n 
    log n
    100n
    n^100
    n^log n
    n^√n
    2^log^3 n
    2^n
    2^n^2
    2^2^n
    

    When comparing any two functions,

    1. cancel out like terms.
    2. apply 'log' on both sides => as many times as possible
    3. substitute very large values for n => 2^100, 2^2^10 etc., (since logs are all base 2)