Computer Sciences > GATE 2026 SET-2 > Algorithms
Consider the following functions, where n is a positive integer.
n1/3, log(n), log(n!), 2log(n)
Which one of the following options lists the functions in increasing order of asymptotic growth rate?
A
log(n), n1/3, 2log(n), log(n!)
B
n1/3, log(n), log(n!), 2log(n)
C
log(n), n1/3, log(n!), 2log(n)
D
2log(n), n1/3, log(n), log(n!)

Correct : a

The correct answer is Option A — log(n), n1/3, 2log(n), log(n!).
To order these functions asymptotically, we first simplify each one into a familiar growth class.
log(n): A standard logarithm, the slowest-growing of all common function classes. It grows slower than any positive power of n.
n1/3: A sub-linear polynomial (cube root of n). Any positive polynomial power of n, however small, grows strictly faster than log(n) asymptotically.
2log(n): When log is base 2, 2log₂(n) = n exactly, placing it in Θ(n). This grows faster than n1/3 since n dominates n1/3 for large n.
log(n!): By Stirling''s approximation, log(n!) ≈ n·log(n) − n, so log(n!) is Θ(n log n). This grows faster than Θ(n), making it the largest of the four.
Putting it all together in increasing order of asymptotic growth: log(n) < n1/3 < 2log(n) < log(n!), which corresponds to Option A.
Option B puts n1/3 before log(n) — incorrect, as log grows slower. Option C places log(n!) before 2log(n) — incorrect ordering at the top. Option D reverses the first two — also incorrect.

Similar Questions

Match the following (P) Prim’s algorithm for minimum spanning tree (i) Backtracking (Q) Floyd-Warshall algorithm fo...
#82 MCQ
Consider the following table Algorithms Design Paradigms (P) Kruskal (i) Divide and Conquer...
#203 MCQ
Consider functions Function 1 and Function 2 expressed in pseudocode as follows: Let f1(n) and f2(n) denote the number of times the statement "x = x + 1" is...
#989 MSQ

Related Topics

asymptotic growth order GATE 2026 GATE CS 2026 Set-2 Q24 log(n!) Stirling approximation GATE 2^log(n) equals n GATE algorithm complexity ordering GATE n^(1/3) vs log(n) GATE increasing asymptotic rate GATE 2026 algorithms GATE CS 2026

Unique Visitor Count

Total Unique Visitors

Loading......