GATE CS 2026 Set 2 Q14 — Asymptotic Worst Case Time and Space Complexity

To find the increasing order of asymptotic growth rate, let us simplify and analyze each of the given functions for large values of $n$:

1. $f_1(n) = \log(n)$
   This is a logarithmic function, which grows extremely slowly compared to any positive polynomial power of $n$.
2. $f_2(n) = n^{1/3}$
   This is a sub-linear polynomial function. Since logarithmic growth is asymptotically slower than any polynomial growth $n^c$ (for $c > 0$), we have: $$\log(n) < n^{1/3}$$
3. $f_3(n) = 2^{\log(n)}$
   Using the logarithmic identity $a^{\log_a(x)} = x$, we simplify this to: $$2^{\log_2(n)} = n$$ Comparing this with $n^{1/3}$, we clearly have $n^{1/3} < n$.
4. $f_4(n) = \log(n!)$
   Using Stirling's approximation, $n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$, which gives: $$\log(n!) = \Theta(n \log n)$$ Comparing this with $f_3(n) = n$, we have $n < n \log n$.

Combining these relations, the increasing order of asymptotic growth rate is:

This matches Option A.