1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Is this the problem in its entirety? $\endgroup$
    – Emily
    Sep 11, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 19:58

2 Answers 2

Reset to default
9
$\begingroup$

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)$.

$\endgroup$
5
  • $\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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 14:49
4
$\begingroup$

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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .