GATE 2015 Example Complexity Analysis

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

I. \hspace{5mm} \Theta(n^4)
II. \hspace{3mm} \Theta(n^5)
III. \hspace{2mm} O(n^5)
\\ IV. \hspace{2mm} \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


because X = \sum_{i=0}^{n} (i^3) \\ = 0^3 + 1^3 + 2^3 + 4^3 + ........+ n^3 \\ = [\frac{n(n+1)}{2}]^2 \\


therefore X = \Theta(n^4) \ \ or \\ \hspace{9mm} = O(n^5) \ \ or \\ \hspace{9mm} = \Omega(n^3)\)

Hence, (C) is Correct


Saikat Das @dassaikat1
19 Oct 2019 05:59 pm
Please explain it.
Rohit Panwar @panwarrohit
19 Oct 2019 11:45 pm

@saikat Das see assume it as a function x..the reason why this is not be theta(n5) because this means that x can be greater then or less that n5 but it is clear that it is always less than n5 i.e O(n5).