GATE Overflow Test Series | Data Structures | Test 1 | Question: 27

Question

Pick the correct order of asymptotic growth rate for the following functions.
$$n^{1/4}, e^n, 3^n, 1.001^n, n^{1000}, n^{\sqrt n}, n!$$

• A. $n^{1/4} <n^{\sqrt n}<1.001^n <e^n< 3^n<  n!< n^{1000}$
• B. $n^{1/4}< n^{1000}<1.001^n <e^n< 3^n<n^{\sqrt n}<  n!$
• C. $1.001^n < n^{1/4}<n^{\sqrt n}<1.001^n <e^n< 3^n< n^{1000}< n!$
• D. $n^{1/4}< n^{1000}<n^{\sqrt n}<1.001^n <e^n< 3^n<  n!$

Answer 1

Polynomial Functions: $n^{1/4}, n^{1000}$

Exponential Functions: $e^n, 3^n, 1.001^n$

Factorial: $n!$

So, it is straightforward that

$n^{1/4} < n^{1000} < 1.001^n < e^n < 3^n < n!$

We only, need to place $n^{\sqrt n}.$

Lets compare $n^{\sqrt n}$ with ${1.001}^n$

By logarithm rule, $n^{\sqrt n} = 1.001^{\log_{1.001}n}\sqrt n = 1.001 ^{\sqrt n \log_{1.001} n} $

Now, comparing the exponent parts, we get
$\sqrt n \log_{1.001} n$ and $n$

$\implies \log_{1.001}$ and $\sqrt n.$

Now, $\log n < \sqrt n$ (Proof see below).

So, we get $n^{\sqrt n} < 1.001^n.$

So, the correct order is

$n^{1/4}< n^{1000}<n^{\sqrt n}<1.001^n <e^n< 3^n<  n!$

Option D.

---

$\log n = 2 \log n^{0.5} = 2 \log \sqrt n < \sqrt n $