GATE CSE 2015 Set 3 | Question: 4

Question

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

1. $\Theta(n^4)$
2. $\Theta(n^5)$
3. $O(n^5)$
4. $\Omega(n^3)$

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

• A. Only I
• B. Only II
• C. I or III or IV but not II
• D. II or III or IV but not I

Comments

A doubt for this question as in to compute the ∑ i³  we need a loop which runs in O(n) time but the mathematical expression for evaluating the same is O(n⁴) , why should we consider the latter?

---

worst case is 0(n^4) then why option 3 is taken right

---

For those who do not know the sum of cubes formula can apply this approach :

$1^3+2^3+3^3+4^3+...n^3  $

Now, replace every digit with n, then series becomes like :

$n^3+n^3 + n^3+….+n^3 $

We can also say that:

$1^3+2^3+3^3+4^3+...n^3 < n^3+n^3 + n^3+….+n^3  $

And , $n^3+n^3 + n^3+….+n^3 $ is basically $(n\hspace{2mm} times)$.

So , it becomes $O(n^4)$

---

same doubt bro

Answer 1

Sum of the cubes of the first nn natural numbers is given by (n(n+1)/2)2(n(n+1)/2)2  which is Θ(n4)Θ(n4).

 (C) is correct.