edited by
16,434 views
57 votes
57 votes

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

  1. Only I
  2. Only II
  3. I or III or IV but not II
  4. II or III or IV but not I
edited by

5 Answers

Best answer
70 votes
70 votes

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.

edited by
42 votes
42 votes
Caption
6 votes
6 votes

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.

1 votes
1 votes

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}$

edited by
Answer:

Related questions

67 votes
67 votes
11 answers
1
go_editor asked Feb 15, 2015
17,241 views
Let $f(n) = n$ and $g(n) = n^{(1 + \sin \: n)}$, where $n$ is a positive integer. Which of the following statements is/are correct?$f(n) = O(g(n))$$f(n) = \Omega(g(n))$On...
60 votes
60 votes
5 answers
3
44 votes
44 votes
5 answers
4
go_editor asked Feb 15, 2015
10,735 views
Let $G$ be a connected undirected graph of $100$ vertices and $300$ edges. The weight of a minimum spanning tree of $G$ is $500$. When the weight of each edge of $G$ is i...