I am new to the Big O notation in regards to algorithm design. I have had some exposure to it but I am not sure how to find the algorithmic complexity of a given function for a summation. If someone can point me in the right direction to solve this problem that would be great.

The Problem:

Prove that $\sum_{i=1}^n i^2$ is $O(n^3)$.

I am not sure how this complexity is derived because in my own mind I feel that the complexity is closer to $n$ for each value in the list of $i$ values.

  • $\begingroup$ Is this the problem in its entirety? $\endgroup$ – Emily Sep 11 '12 at 15:06
  • 5
    $\begingroup$ I think the most important thing is to understand that what you're trying to find is not the complexity of computing the value; rather, you're trying to figure out how the value of the sum itself, as a function of $n$, behaves as $n\rightarrow\infty$. $\endgroup$ – Steven Stadnicki Sep 11 '12 at 15:06
  • $\begingroup$ Yes this is the problem in its entirety. @StevenStadnicki Yes that is basically what I am trying to figure out. Once I can find out the behavior of f(n) and how that relates to the complexity I feel that I would be all set. $\endgroup$ – Michael Guantonio Sep 11 '12 at 15:12
  • 2
    $\begingroup$ @MichaelGuantonio The point is that complexity doesn't actually factor into this problem at all; it may motivate it, but the $O()$ notation is much broader than just complexity and it's really worthwhile to try and divorce the two in your mind. Once you understand the behavior of this sum you can relate it back to complexity, but I'd suggest not thinking about complexity at all while you work this problem. $\endgroup$ – Steven Stadnicki Sep 11 '12 at 15:13
  • $\begingroup$ @StevenStadnicki Sorry, the computer science student in me is trying to make since of it all. This means creating relations that are not there. $\endgroup$ – Michael Guantonio Sep 11 '12 at 19:58

You seem to be confused by what $O(\cdot)$ really means. It doesn't inherently have anything to do with algorithms; the definition is as follows:

Given two functions, $f$ and $g$, we say that $g$ is $O(f)$ if there exists some constants $c$ and $n_0$ such that $g(n) \le c \cdot f(n)$ for all $n \ge n_0$.

For your problem, \begin{align*} \sum_{i=1}^n i^2 \le \sum_{i=1}^n n^2 = n^3 \text{$\quad$for $n \ge 0$}\\ \end{align*}

Thus by definition, $\sum_{i=1}^n i^2$ is $O(n^3)$.

  • $\begingroup$ Still not quite sure how you got this. I can see that you took the general i case and said that it was less than or equal to the n max case. But how you determined because of that the complexity is $O(n^{3})$ baffles me. $\endgroup$ – Michael Guantonio Sep 11 '12 at 20:16
  • 1
    $\begingroup$ Read the definition again. We just need to find $c$ and $n_0$ such that $\sum_{i=1}^n i^2 \le cn^3$ for all $n \ge n_0$. The steps I took above show that $c=1$ and $n_0 = 0$ are valid witnesses. That is, $\sum_{i=1}^n i^2$ is always less than $n^3$ and therefore by definition is $O(n^3)$. $\endgroup$ – Zach Langley Sep 11 '12 at 22:34
  • $\begingroup$ @MichaelGuantonio (The word "complexity" does not apply here. There is no computation, only a comparison of functions.) $\endgroup$ – Zach Langley Sep 14 '12 at 14:55
  • $\begingroup$ How can I deal with a more general function for this problem. Like proving for the general case that $$\sum_{i=1}^n i^k is O(n^{k-1})$$ $\endgroup$ – Michael Guantonio Sep 14 '12 at 22:48
  • $\begingroup$ @MichaelGuantonio You won't be able to prove that because it's not true. $\sum_{i=1}^n i^k \ge n^k$ so the function is $\omega(n^{k-1})$. If you meant to switch the exponents, the exact same techniques I used above will work. $\endgroup$ – Zach Langley Sep 15 '12 at 14:49

By the very definition of $O$, you have to prove that there is an $N \in \mathbb N$ and a $C \ge 0$ such that \[ \sum_{i=1}^n i^2 \le C n^3, \quad n \ge N, \] right?

But now for each $n$ and each $1 \le i \le n$ we have $i^2 \le n^2$, so \[ \sum_{i=1}^n i^2 \le \sum_{i=1}^n n^2 = n^3, \] and we are done with $N = 1$, $C = 1$.


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.