GATE CS 2021 Set 1 Q3 — Asymptotic Worst Case Time and Space Complexity

To compare the asymptotic growth rates of the given functions, we can take the logarithm (base $2$) of each function. Since the logarithm is a strictly increasing function, the order of growth of the logarithms will be the same as the order of growth of the original functions.

Let's analyze each function:

1. For $f_1 = 10^n$: $$\log_2(f_1) = \log_2(10^n) = n \log_2 10 \approx 3.32 n \in \Theta(n)$$
2. For $f_2 = n^{\log n}$ (assuming base $2$ for the exponent log): $$\log_2(f_2) = \log_2\left(n^{\log_2 n}\right) = \log_2 n \cdot \log_2 n = (\log_2 n)^2 \in \Theta((\log n)^2)$$
3. For $f_3 = n^{\sqrt{n}}$: $$\log_2(f_3) = \log_2\left(n^{\sqrt{n}}\right) = \sqrt{n} \log_2 n \in \Theta(\sqrt{n} \log n)$$

Now, we compare the growth rates of the logarithmic terms for large values of $n$:

• Polylogarithmic functions grow slower than sub-linear polynomial functions: $$(\log_2 n)^2 < \sqrt{n} \log_2 n$$
• Sub-linear polynomial functions grow slower than linear functions: $$\sqrt{n} \log_2 n < n$$

Thus, the order of growth of the logarithms is: $$\log_2(f_2) < \log_2(f_3) < \log_2(f_1)$$

This directly translates to the growth rate of the original functions: $$f_2 < f_3 < f_1$$

Therefore, the increasing order of asymptotic growth rate is $f_2, f_3, f_1$.