GATE CS 2015 Set 3 Q4 — Asymptotic Worst Case Time and Space Complexity

First, let us find the exact closed-form expression for the given sum of cubes:

Since the highest degree term in the polynomial is $n^4$, the exact asymptotic growth rate of the sum is:

Now, let us evaluate each of the given choices for $X$ based on the definitions of asymptotic notations:

1. $\Theta(n^4)$: Correct. Since the sum is a polynomial of degree $4$, its tight bound is indeed $\Theta(n^4)$.
2. $\Theta(n^5)$: Incorrect. A function of order $n^4$ cannot be asymptotically tight with $n^5$.
3. $O(n^5)$: Correct. By definition of Big-O (upper bound), any function that is $\Theta(n^4)$ is also $O(n^5)$ because $n^4 \le c \cdot n^5$ for sufficiently large $n$.
4. $\Omega(n^3)$: Correct. By definition of Big-Omega (lower bound), any function that is $\Theta(n^4)$ is also $\Omega(n^3)$ because $n^4 \ge c \cdot n^3$ for sufficiently large $n$.

Thus, the equality remains correct if $X$ is replaced by I, III, or IV, but not II.