Consider the following three functions. \(f_1 = 10^n\)\(f_2 = n^{log \…
2021
Consider the following three functions.
\(f_1 = 10^n\)\(f_2 = n^{log \ n}\)\(f_3 = n^{\sqrt n}\)
Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
- A.
\(f_3\ \ f_2 \ \ f_1\) - B.
\(f_2\ \ f_1 \ \ f_3\) - C.
\(f_1\ \ f_2 \ \ f_3\) - D.
\(f_2\ \ f_3 \ \ f_1\)
Attempted by 322 students.
Show answer & explanation
Correct answer: D
Key idea: compare growth by taking natural logarithms of each function.
For f2(n) = n^{log n}: ln(f2) = (log n) * ln n = Theta((ln n)^2) (log base is a constant factor and does not affect asymptotics).
For f3(n) = n^{sqrt n}: ln(f3) = sqrt(n) * ln n = Theta(sqrt(n) * ln n).
For f1(n) = 10^n: ln(f1) = n * ln 10 = Theta(n).
Compare these three logarithmic growth rates for large n: (ln n)^2, sqrt(n) * ln n, and n.
Since sqrt(n) grows faster than ln n, we have (ln n)^2 << sqrt(n) * ln n. And since n grows faster than sqrt(n) * ln n (because n / (sqrt(n) * ln n) = sqrt(n) / ln n -> infinity), we get sqrt(n) * ln n << n.
Therefore the functions in increasing order of growth are: n^{log n} < n^{sqrt n} < 10^n.
A video solution is available for this question — log in and enroll to watch it.