GATE CSE 2026 | Set 2 | Question: 14

Question

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

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

• A. $\log (n), n^{1 / 3}, 2^{\log (n)}, \log (n!)$
• B. $n^{1 / 3}, \log (n), \log (n!), 2^{\log (n)}$
• C. $\log (n), n^{1 / 3}, \log (n!), 2^{\log (n)}$
• D. $2^{\log (n)}, n^{1 / 3}, \log (n), \log (n!)$

Comments

https://gateoverflow.in/?qa=blob&qa_blobid=14914786636693531353

Answer 1

Asymptotically, $log(n!)=nlog(n)$  $ \&$ $2^{log(n)}=n$

So:  $log(𝑛) , 𝑛^{1/3}, 2^{log(𝑛) }, log(𝑛!) $ is correct order

Comments

Can you tell me where did you learned these equalities I am struggling with asymptotic notation comparisons?

---

@S_Sandeep
https://www.youtube.com/watch?v=-l0Gy_i47NE

Answer 2

by taking log we can get the answer as Option D.

$n^{1/3}  → 1/3 *log(n)$

$log(n!)$ we can write as $log(n^n)$ $→n *log(n)$

$log(n) →log(log(n))$

$2^{log(n)}$ $→log n* log2$

$log(log(n)) ≪ 1/3 *log(n) ≪ log n* log2 ≪ n *log(n)$

Answer 3

$\textbf{Points to consider}$

• $\text{You can take any  smallest power of $n$ eg.  $n^{\frac{1}{100}} $ that will be still asymtotically greater than $log n$.}$
• $\text{$log(n!)= \theta(nlogn) $  [Acc to Sterling's Approximation].}$
• $\text{ $2^{logn}=  n  \space\space [a^{\log_a x} = x]$}$

$\text{Consider the points above we can eliminate option B and D , as we know $ logn < n^{1/3}$ }$
$\text{Now $n$ is smaller than $nlogn$ so we can say that $ 2^{logn} <log(n!)$}.$

$\text{Both conditions are matched by OPTION A  i.e CORRECT}.$

 

 

 A)     $log(n) < n^{1/3} <2^{logn}  < log (n!) . $ 

Answer 4

log(n!) = nlogn by striling approximation

2^logn = n by log property

so our options are: n^1/3 , logn, nlogn, n

evidently: logn < n^1/3 < n< nlogn

correct answer is option A

Answer 5

coption A