Consider the equality \(\displaystyle{\sum_{i=0}^n} i^3 = X\) and the…
2015
Consider the equality \(\displaystyle{\sum_{i=0}^n} i^3 = X\) and the following choices for \(X\)
I. \(\Theta(n^4)\)
II. \(\Theta(n^5)\)
III. \(O(n^5)\)
IV. \(\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
Attempted by 200 students.
Show answer & explanation
Correct answer: C
Answer: The correct replacement is Theta(n^4), and therefore the statements O(n^5) and Omega(n^3) are also true; Theta(n^5) is false.
Derivation and justification:
Closed form: the sum equals (n(n+1)/2)^2, which behaves like n^4/4 for large n.
Theta(n^4) holds because the expression is bounded above and below by constant multiples of n^4 for sufficiently large n.
O(n^5) holds because any function that is Theta(n^4) is also O(n^5): n^4 ≤ C·n^5 for n ≥ 1.
Omega(n^3) holds because n^4 grows at least as fast as a constant times n^3 for large n.
Theta(n^5) does not hold because the function grows like n^4, not n^5; it is not both O(n^5) and Omega(n^5).
A video solution is available for this question — log in and enroll to watch it.