GATE CS 2026 Set 2 Q.24: Asymptotic Analysis and Time/Space Complexity

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

n^{1/3}, \quad \log(n), \quad \log(n!), \quad 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$ .

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

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

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

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

Official answer and solution

Solution

Simplify $2^{\log_2(n)} = n$ and $\log_2(n!) = \Theta(n \log n)$ , then order the four growth rates.

Since the logarithm base is $2$ :

$\log_2(n)$ grows logarithmically.
$n^{1/3}$ grows polynomially with exponent $1/3$ .
$2^{\log_2(n)} = n$ grows linearly (exponent $1$ ).
By Stirling's approximation, $\log_2(n!) = \Theta(n \log n)$ , which grows faster than $n$ .

Thus the increasing order of asymptotic growth is:

\log(n) \prec n^{1/3} \prec 2^{\log(n)} \prec \log(n!)

Final answer

Option (A)

Common trap

Mistaking $2^{\log_2(n)}$ for an exponential function instead of $n$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 24 of 65
Section: Computer Science and Information Technology

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.