Search code examples
algorithmcomputer-science

Order of growth rate in increasing order

Arrange the following functions in increasing order of growth rate (with g(n) following f(n) in your list if and only if f(n)=O(g(n))).

a)2^log(n)  
b)2^2log(n)  
c)n^5/2  
d)2^n^2  
e)n^2 log(n)

So i think answer is in increasing order is CEDAB
is it correct? i have confusion in option A and B. i think option A should be at first place.. less one i mean so please help how to solve this. This question I faced in algorithm course part 1 assignment (Coursera) .

Solution

  • Firstly, any positive power of n is always greater than log n, so E comes before C, not after.

    Also, D comes after every other function, as either interpretation of 2^n^2 (could be 2^(n^2) or (2^n)^2 = 2^(2n); I could be wrong in ignoring BIDMAS though...) are exponentials of n itself.

    Taking log to be base a, some arbitrary constant:

    a) enter image description here

    b) enter image description here

    Thus, unfortunately, the actual order depends of the value of a, e.g. if the value of

    enter image description here

    is greater than 2, then A comes after E, otherwise before. Curiously the base of the log term in E is irrelevant (it still maintains its place).