0
$\begingroup$

Please could someone advise on my solution to the following problem. Am I wording this right or could you offer a better way?

Question is to show that $S_n =O(n^3)$ where $S_n = \sum_{k=1}^n(k^2)$

Solution: $\begin{align*}S_n &= n(a_1 + a_n)/ 2 \quad\leftarrow \text{sum of series} \\ &= n(1 + n^2)/2 \\ &= n/2 + n^3/2\end{align*}$

Since $n^3$ is the dominant term the Big-O estimate is $O(n^3)$

Should this be worded differently?

cheers

  • 0
    If you click the "edit"-button on the bottom right of the question box, you can see how I, or rather Brian M. Scott, formatted your question. If you don't want to change anything, you can just press "Cancel"2012-10-09

1 Answers 1

1

As Arthur pointed out in the comments, your exact expression for $\sum_{k=1}^nk^2$ is wrong, but you don’t actually need to know one in order to show that $S_n$ is $O(n^3)$: just note that $S_n=\sum_{k=1}^nk^2\le\sum_{k=1}^nn^2=n^3\;.$

  • 0
    @bosra: They aren’t increasing by a common ratio: $\frac{(k+1)^2}{k^2}=\left(\frac{k+1}k\right)^2=\left(1+\frac1k\right)^2$, whose value depends on $k$. The sequence of squares is neither arithmetic nor geometric. Either you need the actual formula for the sum of the first $n$ squares, which Arthur gave in his first comment, or you might as well just use the very simple argument that I gave in my answer.2012-10-09