0
$\begingroup$

Just starting my Data Structures class, and this is one of several questions for my HW in one question. (I.e. this is 1a, but there's b-f too). I have no clue where to even start, the book doesn't lend any hints, it doesn't even explain how to use the sigma notation in this context (I know what sigma is), and my teacher barely speaks English. So can somebody please help me figure out what I'm supposed to do when the book asks the question:

Prove $\sum\limits_{i=1}^n i^2$ is $O(n^3)$ and more generally, $\sum\limits_{i=1}^n i^k$ is $O(n^{k+1})$.

Any help is appreciated. Thanks.

$\endgroup$
5
$\begingroup$

$\sum\limits_{i=1}^n i^k = 1^k + 2^k + \cdots + n^k \le n^k + n^k \cdots + n^k = n(n^k) = n^{k+1} \implies \sum\limits_{i = 1}^n i^k = O(n^{k+1})$.

Note, if the question asked about proving $\sum\limits_{i = 1}^n i^k = \Theta(n^{k+1})$, then this proof won't work.

$\endgroup$
  • $\begingroup$ Makes sense (sort of, still wrapping my head around the notation), for completeness sake, and assuming it's not too difficult, would you mind putting up how it would look if it did as for theta? (It did not, it was O). $\endgroup$ – David Oct 1 '14 at 11:01
  • 1
    $\begingroup$ You can use this question that I asked recently to prove that it is in $\Theta(n^{k+1})$. $\endgroup$ – taninamdar Oct 1 '14 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.