Question

Consider the following functions, where 𝑛 is a positive integer.
𝑛1/3 , log(𝑛) , log(𝑛!), 2log(𝑛)
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(𝑛) , 𝑛1/3, 2log(𝑛) , log(𝑛!)
• B. 𝑛1/3, log(𝑛) , log(𝑛!) , 2log(𝑛)
• C. log(𝑛) , 𝑛1/3, log(𝑛!) , 2log(𝑛)
• D. 2log(𝑛) , 𝑛1/3, log(𝑛) , log(𝑛!)

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)