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