GATE CS 2000 Q2.17 — Asymptotic Worst Case Time and Space Complexity

To find the correct relationship between the given functions, let us analyze and simplify them asymptotically:

1. Analyze $f(n)$ and $g(n)$:

   We are given:

   $$f(n) = 3n^{\sqrt{n}}$$ $$g(n) = 2^{\sqrt{n}\log_{2}n}$$

   Using the identity $n = 2^{\log_{2}n}$, we can rewrite $f(n)$ as:

   $$f(n) = 3 \cdot \left(2^{\log_{2}n}\right)^{\sqrt{n}} = 3 \cdot 2^{\sqrt{n}\log_{2}n}$$

   Comparing this with $g(n)$:

   $$f(n) = 3 \cdot g(n)$$

   Since $f(n)$ is a constant multiple of $g(n)$, they grow at the exact same rate asymptotically. Thus:

   $$f(n) = \Theta(g(n))$$

   This implies both of the following are true:

   • $f(n) = O(g(n))$
   • $g(n) = O(f(n))$
2. Analyze $h(n)$:

   We have $h(n) = n!$. By Stirling's approximation, $n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$, which grows much faster than $n^{\sqrt{n}}$. Therefore, $h(n)$ is strictly larger than both $f(n)$ and $g(n)$ asymptotically, meaning $h(n)$ is neither $O(f(n))$ nor $O(g(n))$.

Let us evaluate the given options:

• A. $h(n)$ is $O(f(n))$: False, because $h(n)$ grows much faster than $f(n)$.
• B. $h(n)$ is $O(g(n))$: False, because $h(n)$ grows much faster than $g(n)$.
• C. $g(n)$ is not $O(f(n))$: False, since $g(n) = O(f(n))$ is true.
• D. $f(n)$ is $O(g(n))$: True, since $f(n) = 3 \cdot g(n)$.