The GATE Grind

GATE 2021 CS – Question 13

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice

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?

  1. $f_3, f_2, f_1$
  2. $f_2, f_1, f_3$
  3. $f_1, f_2, f_3$
  4. $f_2, f_3, f_1$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $f_2, f_3, f_1$

Explanation

Taking logs: $\log f_2 = \log^2 n$, $\log f_3 = \sqrt{n}\log n$, $\log f_1 = n\log 10$. Growth order is $f_2 < f_3 < f_1$.