The GATE Grind

GATE 2026 CS (CS2) – Question 24

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice

Consider the following functions, where $n$ is a positive integer: $n^{1/3}$, $\log n$, $\log(n!)$, and $2^{\log n}$. Which one of the following options lists the functions in increasing order of asymptotic growth rate?

Note: assume the base of $\log$ to be 2.

  1. $\log n$, $n^{1/3}$, $2^{\log n}$, $\log(n!)$
  2. $n^{1/3}$, $\log n$, $\log(n!)$, $2^{\log n}$
  3. $\log n$, $n^{1/3}$, $\log(n!)$, $2^{\log n}$
  4. $2^{\log n}$, $n^{1/3}$, $\log n$, $\log(n!)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $\log n$, $n^{1/3}$, $2^{\log n}$, $\log(n!)$

Explanation

We compare the growth rates: $\log n$ grows more slowly than any positive power of $n$, so $\log n < n^{1/3}$. Also, $2^{\log n}=n$ when the logarithm base is 2. Finally, by Stirling's approximation, $\log(n!) = \Theta(n\log n)$, which grows faster than $n$. Hence the increasing order is $$\log n < n^{1/3} < 2^{\log n} < \log(n!).$$ Therefore, option (A) is correct.