GATE CS 2011 Q37 — Asymptotic Worst Case Time and Space Complexity

To find the increasing order of asymptotic complexity, we compare the growth rates of the functions as $n \to \infty$:

1. Comparing $f_3(n)$ and $f_2(n)$:
   $f_3(n) = n \log_2 n$ and $f_2(n) = n^{1.5} = n \cdot n^{0.5}$. Since $\log_2 n < n^{0.5}$ for large $n$, we have $f_3(n) < f_2(n)$.
2. Comparing $f_2(n)$ and $f_4(n)$:
   Taking the base-2 logarithm of both functions:
   $\log_2(f_2(n)) = 1.5 \log_2 n$
   $\log_2(f_4(n)) = (\log_2 n)^2$
   Since $1.5 \log_2 n < (\log_2 n)^2$ for large $n$, we have $f_2(n) < f_4(n)$.
3. Comparing $f_4(n)$ and $f_1(n)$:
   Expressing $f_4(n)$ with base 2 gives $f_4(n) = 2^{(\log_2 n)^2}$. Since $(\log_2 n)^2 < n$ for large $n$, we have $f_4(n) < f_1(n)$.

Combining these relations gives the increasing order of complexity: $$f_3 < f_2 < f_4 < f_1$$

Hence, the correct option is A.