Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Is this the problem in its entirety? –  Arkamis Sep 11 '12 at 15:06
5  
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$. –  Steven Stadnicki Sep 11 '12 at 15:06
    
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. –  Michael Guantonio Sep 11 '12 at 15:12
2  
@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. –  Steven Stadnicki Sep 11 '12 at 15:13
    
@StevenStadnicki Sorry, the computer science student in me is trying to make since of it all. This means creating relations that are not there. –  Michael Guantonio Sep 11 '12 at 19:58
add comment

2 Answers

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

share|improve this answer
    
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. –  Michael Guantonio Sep 11 '12 at 20:16
1  
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)$. –  Zach Langley Sep 11 '12 at 22:34
    
@MichaelGuantonio (The word "complexity" does not apply here. There is no computation, only a comparison of functions.) –  Zach Langley Sep 14 '12 at 14:55
    
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})$$ –  Michael Guantonio Sep 14 '12 at 22:48
    
@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. –  Zach Langley Sep 15 '12 at 14:49
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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