GATE CS 2017 Set 1 Q04 — Asymptotic Worst Case Time and Space Complexity

To arrange the given functions in increasing order of asymptotic complexity, we analyze their growth rates as $n \to \infty$:

1. $\frac{100}{n}$: As $n$ grows very large, this function approaches $0$. Thus, it has the slowest growth rate (it actually decreases), which is asymptotically smaller than any constant: $$\frac{100}{n} = o(1)$$
2. $10$: This is a constant function. Its value remains $10$ regardless of $n$: $$10 = \Theta(1)$$
3. $\log_{2}n$: This is a logarithmic function. It grows to infinity, but extremely slowly compared to any positive polynomial power of $n$: $$\log_{2}n = o(n^c) \quad \text{for any } c > 0$$
4. $\sqrt{n}$: This is a fractional power function ($n^{0.5}$). It grows faster than logarithmic functions but slower than linear functions: $$\sqrt{n} = o(n)$$
5. $n$: This is a linear function, which grows the fastest among all the given functions.

Comparing these growth rates, we get the following chain of asymptotic dominance:

Therefore, the correct increasing order is $\frac{100}{n}$, $10$, $\log_{2}n$, $\sqrt{n}$, $n$, which corresponds to option B.