GATE 2026 CS2 Q.24: solution and answer

GATE 2026 · CS2Q.24 · 1 mark · MCQ

Consider the following functions, where $n$ is a positive integer.

n^{1/3}, lo g (n), lo g (n!), 2^{l o g (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.

(A)
$lo g (n)$ , $n^{1/3}$ , $2^{l o g (n)}$ , $lo g (n!)$
(B)
$n^{1/3}$ , $lo g (n)$ , $lo g (n!)$ , $2^{l o g (n)}$
(C)
$lo g (n)$ , $n^{1/3}$ , $lo g (n!)$ , $2^{l o g (n)}$
(D)
$2^{l o g (n)}$ , $n^{1/3}$ , $lo g (n)$ , $lo g (n!)$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The correct answer is (A): log(n), n^{1/3}, 2^{log(n)}, log(n!) — in increasing order of asymptotic growth rate.

Official answer: ASource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

Since the log base is given as 2 (per the note), $2^{l o g (n)} = 2^{l o g_{2} (n)} = n$ by the definition of logarithm as the inverse of exponentiation.
$lo g (n)$ grows slower than any positive power of $n$ (in particular slower than $n^{1/3}$ ), so it is the smallest of the four functions.
Since the exponent $1/3 < 1$ , $n^{1/3} = o (n)$ . So $n^{1/3}$ grows more slowly than $n = 2^{l o g (n)}$ .
By Stirling's approximation, $lo g (n!) = Θ (n lo g n)$ , which grows strictly faster than $n$ itself (since $lo g n \to \infty$ as $n \to \infty$ ).
Combining all comparisons: $lo g (n) < n^{1/3} < n (= 2^{l o g (n)}) < n lo g n (= lo g (n!))$ .
This increasing-growth-rate order — $lo g (n), n^{1/3}, 2^{l o g (n)}, lo g (n!)$ — is exactly option (A).

KEY IDEA

Simplify each function to a standard growth class using $2^{l o g_{2} (n)} = n$ and $lo g (n!) = Θ (n lo g n)$ (Stirling), then order the resulting classes: $lo g n ≪ n^{1/3} ≪ n ≪ n lo g n$ .

WATCH OUT FOR

Forgetting that "log" here means log base 2 (as stated in the note) and mis-simplifying $2^{l o g (n)}$ ; a common error is to treat $2^{l o g (n)}$ as growing faster than $n$ (e.g., confusing it with $n^{l o g (n)}$ or $2^{n}$ ), or to assume $lo g (n!)$ grows only like $lo g (n)$ rather than $Θ (n lo g n)$ by Stirling's approximation.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 14 Complexity questions, with notes

GATE 2026 CS2 Q.24: solution and answer

Answer and solution

More Complexity questions