Order of growth rate in increasing order

Question

This question is related to maths, so I post here. Actually it's a computer science question and I am facing this type of question while learning Design and Analysis of Algorithms, but we all know that computer science has complete relation with maths.

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 the answer, in increasing order, is CEDAB.

Is it correct? I have confusion in option A and B. I think option A should be first... the one with the lower growth rate I mean. Please help me solve this. I faced this question in algorithm course part 1 assignment (Coursera).

Answer 1

Okay, so $2^{log(n)} < n$ because the logarithm base is greater than 2. Now you might want to see that $2^{2 log(n)} = (2^{log(n)})^2 $ to realise that B is faster growing than A.

Exponential growth is always faster than polynomial, so D has to be the fastest growing one. Furthermore, C > E because $n > log(n)$ (the factor $\frac{1}{2}$ has absolutely no effect here). Finally, E > B, because $n^2 > x^2$, where $x<n$ (see the equation on my first line).

So it is ABECD

Answer 2

@thebadguy is correct. The answer is AECBD.

Letter B is supposed to be $2^{2^{\log n}}$ and not $2^{2\log n}$. They are different.

In this question, all logs are assumed to be base-2.

To answer, recall some properties of logarithm:

$2^{\log_2 n} = n$

$a\log_2 (n) = \log_2(n^a)$

---

Simplifying A and B:
A: $n$
B: $2^n$
C: $n^{5/2} = n^{2.5}$
D: $2^{n^2}$
E: $n^2\log n$

Applying the order of growth rate of functions$^1$,

A < E < C < B < D

---

$^1$ snippet from page 39 of The Algorithm Design Manual 3e by Skiena

Answer 3

Take the limit to the infinity of quotient of each combination and if the result is $0$ or more generally a constant, what it means? and if the result is $\infty$?

That is the way to check what function grows faster that other when $n$ grows.