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.

  • 0
    Is this the problem in its entirety?2012-09-11
  • 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$.2012-09-11
  • 0
    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.2012-09-11
  • 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.2012-09-11
  • 0
    @StevenStadnicki Sorry, the computer science student in me is trying to make since of it all. This means creating relations that are not there.2012-09-11

2 Answers 2