JEST TCS 2025 | Section A (MCQ) | Question: 23

Question

Let $f(n) := 2^n, g(n) := n$ and $h(n) :=$ $n^{log n}$. Which of the following statements is true$?$

• A. log $h(n) = O(g(n))$ and log $h(n) = \Omega$(log $f(n)).$
• B. $f(n)= O(g(n))$ and $f(n)= O(h(n))$.
• C. $g(n) = \Theta$(log $f(n))$ and $h(n) = O(f(n))$.
• D. log $f(n) = O(g(n))$ and log $f(n) = O$(log $h(n)).$

Answer 1

\(f(n)=2^n\), \(g(n)=n\), and \(h(n)=n^{\log n}\).

\[
\log f(n)
= \log\bigl(2^n\bigr)
= n\cdot\log 2
= \Theta(n).
\]

Also,
\[
\log h(n)
= \log\bigl(n^{\log n}\bigr)
= (\log n)^2.
\]

Therefore,
\[
g(n)
= n
= \Theta\bigl(\log f(n)\bigr).
\]

For \(h(n)\):
\[
\log_2 h(n)
= \log_2\bigl(n^{\log_2 n}\bigr)
= \log_2 n \cdot \log_2 n
= (\log_2 n)^2.
\]

For \(f(n) = 2^n\):
\[
\log_2 f(n)
= \log_2(2^n)
= n.
\]

 

Since for large \(n\), \((\log_2 n)^2 \ll n\),we get:
\[
 \quad h(n) = O(2^n).
\]
\[
\boxed{\text{Option C is correct.}}
\]