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
    @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

9

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

  • 0
    @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.2012-09-15
4

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