Question

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 \)

Hint:

To compare fast-growing functions, convert them into exponential form and compare exponents.

Answer 1

The Correct Option is D

Step 1: Rewrite functions in exponential form.
We rewrite each function using exponentials to compare growth rates:
\[ f_2 = n^{\log n} = e^{(\log n)^2}, f_3 = n^{\sqrt{n}} = e^{\sqrt{n}\log n}, f_1 = 10^n = e^{n\log 10}. \]

Step 2: Compare exponents.
\[ (\log n)^2 \ll \sqrt{n}\log n \ll n. \] Hence, \( f_2 \) grows slower than \( f_3 \), and \( f_3 \) grows slower than \( f_1 \).

Step 3: Arrange in increasing order.
\[ f_2 < f_3 < f_1. \]