Question

Consider the functions \(n^{1/3},\ \log_2 n,\ \log_2(n!),\ 2^{\log_2 n}\), where \(n\) is a positive integer.
Which option lists the functions in increasing asymptotic growth order?
Assume that the logarithm has base 2.

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

Hint:

Simplify 2 raised to log base 2 of n down to n first, then rank log n, n^(1/3), n, and n log n, using Stirling's approximation for log(n!), by the standard growth rate hierarchy.

Answer 1

The Correct Option is A

Step 1: Simplify each function. \(2^{\log n}\), with log base 2, simplifies to \(n\), since \(2^{\log_2 n} = n\).
Step 2: By Stirling's approximation, \(\log(n!) = \Theta(n \log n)\), which grows faster than any linear function of n.
Step 3: Compare the four functions: \(\log n\) grows slower than \(n^{1/3}\), since any positive power of n beats a logarithm. \(n^{1/3}\) grows slower than \(n\), since the exponent \(1/3 < 1\). \(n\), i.e. \(2^{\log n}\), grows slower than \(n \log n\), i.e. \(\log(n!)\).
Step 4: So the increasing order is: \(\log(n) < n^{1/3} < 2^{\log(n)} < \log(n!)\).
Final Answer: log(n), n^(1/3), 2^log(n), log(n!) (Option A)