GATE CS 2005 Q37 — Asymptotic Worst Case Time and Space Complexity

To find the correct option, let us first solve the given recurrence relation:

We can apply the Master Theorem for divide-and-conquer recurrences of the form $T(n) = aT(n/b) + f(n)$:

• Here, $a = 2$, $b = 2$, and $f(n) = n$.
• We compute $n^{\log_b a} = n^{\log_2 2} = n^1 = n$.
• Since $f(n) = \Theta(n^{\log_b a}) = \Theta(n)$, we fall into Case 2 of the Master Theorem.

Thus, the tight asymptotic bound is:

Now, let us evaluate each option based on the definitions of asymptotic notations:

• Option B: $T(n) = \Theta(n \log n)$ is TRUE as derived above.
• Option D: $T(n) = O(n \log n)$ is TRUE because any function that is $\Theta(g(n))$ is also $O(g(n))$.
• Option A: $T(n) = O(n^2)$ is TRUE because $n \log n$ grows strictly slower than $n^2$ as $n \to \infty$ (i.e., $n \log n = o(n^2) \implies n \log n = O(n^2)$).
• Option C: $T(n) = \Omega(n^2)$ is FALSE because $n \log n$ does not grow at least as fast as $n^2$. Mathematically, $\lim_{n \to \infty} \frac{n \log n}{n^2} = 0$, which means $T(n) = o(n^2)$, making it impossible for $T(n)$ to be $\Omega(n^2)$.

Therefore, the false statement is C.