n1/3, log(n), log(n!), 2log(n)
Which one of the following options lists the functions in increasing order of asymptotic growth rate?
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
Total Unique Visitors