Question
Which of the given options provides the increasing order of asymptotic complexity of functions $f_1, f_2, f_3$ and $f_4$?
$f_1(n) = 2^n$
$f_2(n) = n^{3/2}$
$f_3(n) = n \log_2 n$
$f_4(n) = n^{\log_2 n}$
A.$f_3, f_2, f_4, f_1$
B.$f_3, f_2, f_1, f_4$
C.$f_2, f_3, f_1, f_4$
D.$f_2, f_3, f_4, f_1$
This question i found in one of the entrance examination.I tried solving it but i am getting wrong answer.so i want to verify that is my concept wrong or i am missing something?
Approach
I can write $f_1,f_2,f_3,f_4$ as
$$f_1=e^{n \log_2 2}$$
$$f_2=e^{\frac{3}{2} \log_2 n}$$
$$f_3=e^{ \log (n \log_2 n)}=e^{ \log (n )+\log \log_2 n}$$
$$f_4=e^{\log _2 n \times \log_2 n}$$
So, i am getting sequence as
$f_2, f_3, f_4, f_1$
But answer is given as-:
$f_3, f_2, f_4, f_1$
I am not getting how
$$\frac{3}{2} \log_2 n > \log n +\log \log_2 n$$
Best Answer
Basically, we are trying to calculate the limit $$\lim_{n\to\infty} \frac{n^{3/2}}{n\lg n}$$ (Note that $\log_2(n)$ and $\lg(n$ are asymptotically equavilent.)
Here is my derivation: $$ \begin{aligned} \lim_{n\to\infty} \frac{n^{3/2}}{n\lg n} &= \lim_{n\to\infty}\frac{n^{1/2}}{\lg n} &\text{cancelling out n}\\ &= \lim_{n\to\infty}\frac{\frac{1}{2}n^{-1/2}}{\frac{1}{n}} &\text{L'Hospital's Rule}\\ &= \lim_{n\to\infty}\frac{1}{2}n^{1/2}\\ &= \infty \end{aligned} $$ Hence, $f_3<f_2$. Hope this helps!