GATE CS 2015 Set 3 Q.14 (CS Q.4): Asymptotic Analysis and Time/Space Complexity

Consider the equality $\sum_{i=0}^n i^3 = X$ and the following choices for $X$

\begin{aligned} \text{I.} & \quad \Theta(n^4) \\ \text{II.} & \quad \Theta(n^5) \\ \text{III.} & \quad O(n^5) \\ \text{IV.} & \quad \Omega(n^3) \end{aligned}

The equality above remains correct if $X$ is replaced by

Only I

Only II

I or III or IV but not II

II or III or IV but not I

Official answer and solution

Official answer: C
From: Official GATE 2015 answer key

Solution

Determine the closed form of the sum of cubes and test the validity of each asymptotic relation.

The sum of the first $n$ cubes has the well-known closed form:

\sum_{i=0}^n i^3 = \left(\frac{n(n+1)}{2}\right)^2 = \frac{n^2(n^2 + 2n + 1)}{4} = \frac{n^4 + 2n^3 + n^2}{4}

As $n \to \infty$ , the highest degree term dominates, so:

\sum_{i=0}^n i^3 = \Theta(n^4)

Now evaluate the four candidate choices for $X$ :

Choice I: $\Theta(n^4)$ . Since the sum is a degree-4 polynomial, $\Theta(n^4)$ is an asymptotically tight bound. Correct.
Choice II: $\Theta(n^5)$ . The growth rate is degree 4, not degree 5, so it cannot be $\Theta(n^5)$ . Incorrect.
Choice III: $O(n^5)$ . The big-O notation denotes an asymptotic upper bound. Since $n^4 \le n^5$ for all $n \ge 1$ , any function in $\Theta(n^4)$ is also in $O(n^5)$ . Correct.
Choice IV: $\Omega(n^3)$ . The big-Omega notation denotes an asymptotic lower bound. Since $n^4 \ge n^3$ for all $n \ge 1$ , any function in $\Theta(n^4)$ is also in $\Omega(n^3)$ . Correct.

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

Final answer

Common trap

Assuming equality in asymptotic notation means only tight Theta bounds can replace X, forgetting that Big-O and Big-Omega statements are also valid sets containing Theta(n^4).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 3
Question: 14 of 65, printed as CS Q.4
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source