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: Express the functions in exponential form.
To compare growth rates, rewrite each function using exponentials:

f₂ = n^{log n} = e^{(log n)²}
f₃ = n^√n = e^{√n · log n}
f₁ = 10ⁿ = e^{n · log 10}

---

Step 2: Compare the exponents.
As n → ∞, the growth rates of the exponents satisfy:

(log n)² ≪ √n · log n ≪ n

Hence, f₂ grows slower than f₃, and f₃ grows slower than f₁.

---

Step 3: Final ordering.
Arranging the functions in increasing order of growth:

f₂ < f₃ < f₁