Question:
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.
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.
Show Hint
Simplify $2^{\log n}$ to $n$ first, recall $\log(n!)$ grows like $n\log n$, and remember any positive power of $n$ eventually beats any power of $\log n$.
Updated On: Jul 22, 2026
- \( \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!) \)
Show Solution
Verified By Collegedunia
The Correct Option is A
Solution and Explanation
Step 1: Simplify \(2^{\log(n)}\) since log is base 2.
By definition, \(2^{\log_2(n)} = n\). So this function is really just \(n\), growing linearly.
Step 2: Recall the growth rate of \(\log(n!)\) using Stirling's approximation.
By Stirling's approximation, \(n! \approx \sqrt{2\pi n}\,(n/e)^n\), so
\[ \log(n!) \approx n\log(n) - n\log(e) + \frac{1}{2}\log(2\pi n) \]
The dominant term is \(n\log(n)\), so \(\log(n!)\) grows like \(n\log(n)\), which is strictly faster than plain linear growth \(n\), and faster than everything else in the list, once \(n\) is large.
Step 3: Compare the remaining two functions, \(\log(n)\) and \(n^{1/3}\).
It is a standard asymptotic fact that any positive power of \(n\) eventually grows faster than any power of \(\log(n)\); in particular \(n^{1/3}\), a polynomial growth rate, eventually overtakes \(\log(n)\), a much slower logarithmic rate, even though \(\log(n)\) might look bigger for very small n. As \(n \to \infty\), \(\dfrac{\log(n)}{n^{1/3}} \to 0\), confirming \(\log(n) = o(n^{1/3})\). So \(\log(n)\) grows slower than \(n^{1/3}\).
Step 4: Put all four functions in increasing order of growth rate.
Slowest: \(\log(n)\).
Next: \(n^{1/3}\), since a polynomial beats a logarithm.
Next: \(2^{\log(n)} = n\), since a full linear power beats a fractional power like \(n^{1/3}\) (exponent 1 is bigger than 1/3).
Fastest: \(\log(n!) \approx n\log(n)\), since an extra factor of \(\log(n)\) on top of linear beats plain linear \(n\).
So the increasing order is:
\[ \log(n) \;<\; n^{1/3} \;<\; 2^{\log(n)} \;<\; \log(n!) \]
Step 5: Match with the options and rule out the others.
Option (A) lists exactly \(\log(n), n^{1/3}, 2^{\log(n)}, \log(n!)\), matching Step 4. Option (B) puts \(n^{1/3}\) before \(\log(n)\), which is backwards. Option (C) puts \(\log(n!)\) before \(2^{\log(n)}\), which is backwards since \(n\log(n)\) grows faster than \(n\). Option (D) starts with \(2^{\log(n)}=n\), which is wrong since \(n\) grows faster than both \(\log(n)\) and \(n^{1/3}\), so it cannot be first.
Final Answer:
The increasing order of growth is \(\log(n), n^{1/3}, 2^{\log(n)}, \log(n!)\). \[ \boxed{\text{Option (A)}} \]
By definition, \(2^{\log_2(n)} = n\). So this function is really just \(n\), growing linearly.
Step 2: Recall the growth rate of \(\log(n!)\) using Stirling's approximation.
By Stirling's approximation, \(n! \approx \sqrt{2\pi n}\,(n/e)^n\), so
\[ \log(n!) \approx n\log(n) - n\log(e) + \frac{1}{2}\log(2\pi n) \]
The dominant term is \(n\log(n)\), so \(\log(n!)\) grows like \(n\log(n)\), which is strictly faster than plain linear growth \(n\), and faster than everything else in the list, once \(n\) is large.
Step 3: Compare the remaining two functions, \(\log(n)\) and \(n^{1/3}\).
It is a standard asymptotic fact that any positive power of \(n\) eventually grows faster than any power of \(\log(n)\); in particular \(n^{1/3}\), a polynomial growth rate, eventually overtakes \(\log(n)\), a much slower logarithmic rate, even though \(\log(n)\) might look bigger for very small n. As \(n \to \infty\), \(\dfrac{\log(n)}{n^{1/3}} \to 0\), confirming \(\log(n) = o(n^{1/3})\). So \(\log(n)\) grows slower than \(n^{1/3}\).
Step 4: Put all four functions in increasing order of growth rate.
Slowest: \(\log(n)\).
Next: \(n^{1/3}\), since a polynomial beats a logarithm.
Next: \(2^{\log(n)} = n\), since a full linear power beats a fractional power like \(n^{1/3}\) (exponent 1 is bigger than 1/3).
Fastest: \(\log(n!) \approx n\log(n)\), since an extra factor of \(\log(n)\) on top of linear beats plain linear \(n\).
So the increasing order is:
\[ \log(n) \;<\; n^{1/3} \;<\; 2^{\log(n)} \;<\; \log(n!) \]
Step 5: Match with the options and rule out the others.
Option (A) lists exactly \(\log(n), n^{1/3}, 2^{\log(n)}, \log(n!)\), matching Step 4. Option (B) puts \(n^{1/3}\) before \(\log(n)\), which is backwards. Option (C) puts \(\log(n!)\) before \(2^{\log(n)}\), which is backwards since \(n\log(n)\) grows faster than \(n\). Option (D) starts with \(2^{\log(n)}=n\), which is wrong since \(n\) grows faster than both \(\log(n)\) and \(n^{1/3}\), so it cannot be first.
Final Answer:
The increasing order of growth is \(\log(n), n^{1/3}, 2^{\log(n)}, \log(n!)\). \[ \boxed{\text{Option (A)}} \]
Was this answer helpful?
0
0
Top GATE CS Algorithms Questions
- Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph \( G \) is/are TRUE?
- Let \( G \) be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant \( \alpha \) is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in \( G \) before and after the edge weight update?
- Consider the following recurrence relations. For all \(n > 1\),
\[ T_1(n) = 4T_1\left(\frac{n}{2}\right) + T_2(n) \]
\[ T_2(n) = 5T_2\left(\frac{n}{4}\right) + \Theta(\log_2 n) \]
Assume that for all \(n \leq 1\), \(T_1(n) = 1\) and \(T_2(n) = 1\).
Which one of the following options is correct? - Let \(G(V,E)\) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.
Let \(s \in V\) be a vertex in \(G\). For every \(u \in V\) and for every \(k \geq 0\), let \(d_k(u)\) denote the weight of a shortest path (in terms of weight) from \(s\) to \(u\) of length at most \(k\). If there is no path from \(s\) to \(u\) of length at most \(k\), then \(d_k(u) = \infty\).
Consider the statements:
S1: For every \(k \geq 0\) and \(u \in V\), \(d_{k+1}(u) \leq d_k(u)\).
S2: For every \((u,v) \in E\), if \((u,v)\) is part of a shortest path (in terms of weight) from \(s\) to \(v\), then for every \(k \geq 0\), \(d_k(u) \leq d_k(v)\).
Which one of the following options is correct? - Let \(G(V, E)\) be a simple, undirected graph. A vertex cover of \(G\) is a subset \(V' \subseteq V\) such that for every \((u, v) \in E\), \(u \in V'\) or \(v \in V'\). Let the size of the smallest vertex cover in \(G\) be \(k\). Let \(S\) be any vertex cover of size \(k\).
For a vertex \(v \in V\), which of the following constraints will always ensure that \(v \in S\)?
View More Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions