GATE CS 2021 Set 1 Q.13 (CS Q.3): Asymptotic Analysis and Time/Space Complexity

Consider the following three functions.

f_1 = 10^n, \quad f_2 = n^{\log n}, \quad f_3 = n^{\sqrt{n}}

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

$f_3, f_2, f_1$

$f_2, f_1, f_3$

$f_1, f_2, f_3$

$f_2, f_3, f_1$

Official answer and solution

Official answer: D
From: Official GATE 2021 answer key

Solution

Take the logarithm of each function to compare their asymptotic growth rates.

We are given:

f_1 = 10^n, \quad f_2 = n^{\log n}, \quad f_3 = n^{\sqrt{n}}

Taking the logarithm base 2 of each function:

\log f_1 = \log(10^n) = n \log 10 = \Theta(n)

\log f_2 = \log(n^{\log n}) = (\log n) \cdot (\log n) = (\log n)^2

\log f_3 = \log(n^{\sqrt{n}}) = \sqrt{n} \log n

Comparing the exponents asymptotically as $n \to \infty$ :

(\log n)^2 < \sqrt{n} \log n < n

Because the logarithm is a strictly increasing function, the functions ordered by increasing growth rate are $f_2 < f_3 < f_1$ , which corresponds to option D.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 13 of 65, printed as CS Q.3
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source