GATE CS 1996 Q1.11 — Asymptotic Worst Case Time and Space Complexity

To find which statement is false, let us analyze each option using asymptotic notations:

• Option A: $100n \log n = O\left(\frac{n \log n}{100}\right)$
  In asymptotic analysis, constant factors are ignored. Both functions belong to the complexity class $\Theta(n \log n)$. Since $f(n) = \Theta(g(n)) \implies f(n) = O(g(n))$, this statement is true.
• Option B: $\sqrt{\log n} = O(\log \log n)$
  Let $u = \log n$. The statement becomes $\sqrt{u} = O(\log u)$.
  As $u \to \infty$, any positive power of $u$ (such as $u^{0.5}$) grows strictly faster than any logarithmic function of $u$ (such as $\log u$).
  Mathematically, $$\lim_{u \to \infty} \frac{\sqrt{u}}{\log u} = \infty$$ Therefore, $\sqrt{\log n} = \Omega(\log \log n)$ and is not $O(\log \log n)$. This statement is false.
• Option C: If $0 < x < y$, then $n^x = O(n^y)$
  Since $x < y$, the polynomial $n^x$ grows strictly slower than $n^y$. Thus, $n^x = O(n^y)$ is true.
• Option D: $2^n \neq O(n^k)$ (or $O(nk)$)
  An exponential function $2^n$ grows strictly faster than any polynomial function $n^k$ (or linear function $nk$) for a constant $k$. Thus, $2^n$ cannot be bounded above by $n^k$, making the statement $2^n \neq O(n^k)$ true.

Thus, the false statement is B.