GATE CS 2012 Q18 — Asymptotic Worst Case Time and Space Complexity

By definition, the worst-case running time $W(n)$ represents the maximum time taken by the algorithm over all possible inputs of size $n$:

The average-case running time $A(n)$ is the expected running time over all inputs of size $n$, weighted by their probability of occurrence $P(I)$:

Since the running time $T(I)$ for any individual input $I$ cannot exceed the worst-case running time $W(n)$ (i.e., $T(I) \le W(n)$), we can write:

Since $\sum P(I) = 1$, this simplifies to:

By the definition of Big-O notation, since $A(n) \le 1 \cdot W(n)$ for all $n$, it is always true that:

Why other options are incorrect:

• Option A ($A(n) = \Omega(W(n))$) & Option B ($A(n) = \Theta(W(n))$): These are not always true. For QuickSort, the average-case is $O(n \log n)$ and the worst-case is $O(n^2)$. Here, $A(n)$ grows strictly slower than $W(n)$, so $A(n) \neq \Omega(W(n))$.
• Option D ($A(n) = \text{o}(W(n))$): This is not always true. For MergeSort, both the average-case and worst-case running times are $\Theta(n \log n)$. Since they grow at the same rate, $A(n) \neq \text{o}(W(n))$.