The most effective way to compare these functions is to analyze the growth rate of their logarithms. If $\log (a)>\log (b)$, then $a>b$.
1. Simplify $\log _2(f(n))$
$$
\begin{aligned}
& f(n)=\left(\log _2 n\right)^{\log _2 n} \\
& \log _2(f(n))=\log _2\left(\left(\log _2 n\right)^{\log _2 n}\right) \\
& \log _2(f(n))=\left(\log _2 n\right) \cdot \log _2\left(\log _2 n\right)
\end{aligned}
$$
2. Simplify $\log _2(g(n))$
$$
\begin{aligned}
& g(n)=n^{\sqrt{\log _2 n}}=\left(2^{\log _2 n}\right)^{\sqrt{\log _2 n}}=2^{\left(\log _2 n\right) \cdot \sqrt{\log _2 n}} \\
& \log _2(g(n))=\log _2\left(2^{\left(\log _2 n\right)^{1.5}}\right) \\
& \log _2(g(n))=\left(\log _2 n\right)^{1.5}
\end{aligned}
$$
3. Simplify $\log _2(h(n))$
$$
h(n)=(\sqrt{n})!
$$
We use Stirling's approximation for the logarithm of a factorial, which is $\log (k!) \approx k \log k$
Let $k=\sqrt{n}$.
$$
\begin{aligned}
& \log _2(h(n)) \approx \sqrt{n} \log _2(\sqrt{n})=\sqrt{n} \cdot \frac{1}{2} \log _2(n) \\
& \log _2(h(n)) \approx \frac{1}{2} \sqrt{n} \log _2 n
\end{aligned}
$$
Evaluate the Options
- A. $f(n)$ is $\Omega(g(n))$ : FALSE. This would mean $f(n)$ grows at least as fast as $g(n)$. Our analysis shows it grows slower.
- B. $h(n)$ is $O(g(n))$ : FALSE. This would mean $h(n)$ is bounded above by $g(n)$. Our analysis shows $h(n)$ grows much faster.
- C. $g(n)$ is $O(f(n))$ : FALSE. This is the reverse of the true relationship between $f(n)$ and $g(n)$.
- D. $g(n)$ is $O(h(n))$ : TRUE. Since $h(n)$ is the fastest-growing function in the list, it serves as an asymptotic upper bound for both $f(n)$ and $g(n)$.
