The GATE Grind

GATE 2017 CS – Question 14

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

Consider the following functions from positive integers to real numbers: $10, \sqrt{n}, n, \log_2 n, \frac{100}{n}$.

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

  1. $\log_2 n, \frac{100}{n}, 10, \sqrt{n}, n$
  2. $\frac{100}{n}, 10, \log_2 n, \sqrt{n}, n$
  3. $10, \frac{100}{n}, \sqrt{n}, \log_2 n, n$
  4. $\frac{100}{n}, \log_2 n, 10, \sqrt{n}, n$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\frac{100}{n}, 10, \log_2 n, \sqrt{n}, n$

Explanation

The function $\frac{100}{n}$ tends to 0, so it is the smallest. The constant 10 comes next. Then $\log_2 n$ grows without bound but more slowly than any power of $n$, so it is followed by $\sqrt{n}$ and then $n$.