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 $n$ natural numbers is given by $(n(n+1) / 2) ^ 2$  which is $\Theta(n^4)$. So, I, III and IV are correct. II is wrong.

$\therefore$ (C) is correct.

Comments

• Big $(O)$ behave like $\leq$
• Omega $(\Omega)$  behave like  $\geq$
• Theta $(\Theta)$ behave like  $=$

$X=\left[\frac{n(n+1)}{2}\right]^{2}$

So we can write like $X=\Theta(n^{4})$  becasue $n^{4}=n^{4}$

Similarly, we can write $X=O(n^{5})$ because $n^{4}\leq n^{5}$

and we can also write like this $X=\Omega(n^{3})$ because $n^{4}\geq n^{3}$

But be carefull $X=\Omega(n^{5})$ because $n^{4}\geq n^{5}$  this is wrong.

---

But then, doesn’t option D not satisfy the above equalities as you mentioned. 

Omega (Ω)(Ω)  behave like  ≥

Ω(n^3) ≥  Θ(n^4) 

The worst-case should be greater than the average case, right? 

---

WE ALWAYS TALK ABOUT RHS

ACTUAL FUNCTION N^4 WE TAKE ON LHS

N^3 IS ON RHS

 

SO N^4>= N^3

Answer 2

Caption

Comments

How come you wrote worst case as n^5 pls help here

---

Time complexity came n to the power 4 plus something so what is the worst case it will greater than n to the power 4 thats why it will be n to the power 5

---

Is it like that as far as what i know worst case means TC will never be gereater than that

Ex if TC = O (n^3)

Implies that worst it can go up to n^3 not more than that....

I might be wrong here...correct me if i am anybody..

---

@ aka 53

Big oh notation gives tight upper bound,.. which is obviously bounded by greater worst cases.

 if something is not exceeding n^4 obviously, it will not exceed n^5, n^6,.....

Answer 3

Sum of th e cubes of the first n natural numbers is given by  (n(n+1)/2)^2 which is ϴ(n^4) . So I,III and IV are correct. 

So correct choice is C.

Comments

Sir can you please explain how can we conclude option III and IV are right on the basis of Option I.

and also why option II is wrong ?

Thanks.

---

n^3 =ϴ n^4 ?

---

Big Oh is used for worst case therefore III is right

Answer 4

The sum of cubes of first n numbers is given by: $\left [ \frac{n(n+1)}{2} \right ]^{2}$

Leading term: $n^{4}$

Hence, for big-Oh, anything equal or above $n^{4}$ is correct.

III is correct

 

The sum of the cubes isn't a variable value for a given input. $n^{4}$ is the lower bound, too. So $n^{4}$ or anything less than that works.

IV is correct

 

Both tight upper and lower bounds can be $n^{4}$ because again, the sum of the cubes isn't a variable value for a given input. So, the value would always be $\Theta (n^{4})$

I is correct, and II is incorrect.

 

Option C

 

---

---

 

Another method to solve this is replace 

O by ≤

Ω by  ≥

Θ by  =

And compare with $n^{4}$