GATE CS 2008 Q39 — Asymptotic Worst Case Time and Space Complexity

To compare the growth rates of the functions $f(n) = 2^n$, $g(n) = n!$, and $h(n) = n^{\log n}$, we can take the base-2 logarithm ($\log_2$) of each function for large $n$:

1. For $h(n) = n^{\log_2 n}$:$$\log_2(h(n)) = \log_2\left(n^{\log_2 n}\right) = (\log_2 n)^2$$
2. For $f(n) = 2^n$:$$\log_2(f(n)) = \log_2(2^n) = n$$
3. For $g(n) = n!$:
   Using Stirling's approximation, $\log_2(n!) \approx n \log_2 n - n \log_2 e$. Thus:$$\log_2(g(n)) = \Theta(n \log n)$$

Comparing the growth rates of these logarithmic values for sufficiently large $n$:

Since the logarithm function is strictly increasing, the original functions follow the same ordering in terms of asymptotic growth rate:

From this ordering, we can establish the following relations:

• Since $h(n)$ grows slower than $f(n)$, we have $h(n) = O(f(n))$.
• Since $g(n)$ grows faster than $f(n)$, we have $g(n) = \Omega(f(n))$.

This matches the statements in Option D.