Question

Which of the following options provides the increasing order of asymptotic complexity of functions(Note: Consider log base 2)
a) f1(n)=n logn log logn
b) f2(n)=(n!)^1/n
c) f3(n)=(n^n^(0.5))
d) f4(n)=log n^n

At first glance I thought f2 grow faster but i was wrong.

Ans : f2,f4,f1,f3

Please can somebody help.

Answer 1

$f2$ is not the fastest, in fact it is the slowest in the options.

 Correct order is $f2 < f4 < f1 < f3$

Choose $n = 2^{16}$ and substitute.

$f2 \rightarrow$ $n!^{\frac{1}{n}}$ = $\sqrt[n]{n!}$ $\rightarrow$ Very small value

$f4 \rightarrow$ $log n^n \Rightarrow$ $log((2^{16})^{2^{16}})$ $=$ $log 2^{2^{20}}$ $= 2^{20}$

$f1 \rightarrow$ $nlogn log log n = $ $2^{16} log2^{16} log log 2^{16} = 2^{16} . 16 . 4 = 2^{22}$

$f3 \rightarrow$ $n^{n^{0.5}} = $$((2^{16})^{2^{16}})^{0.5} = (2^{16})^{2^8} = 2^{16*256} = 2^{4096}$