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
    The sum isn't $n(1 + n^2)/2$. This is applicable only when the difference between successive terms is constant. Here it increases by $2$ for each term. Rather, the formula for the sum is $n(n + 1)(2n+1)/6$2012-10-09
  • 0
    Cheers Arthur..What am I doing wrong with the formatting? For instance it does not seem to be displaying the exponent correctly when I use, for example, S_n =O(n^3)..any thoughts?2012-10-09
  • 0
    You need to enclose math within dollar signs, and within double dollar signs when you want bigger expressions in separate lines. This also makes writing actual dollar signs a bit tricky, you need to type a backslash before the \$-sign.2012-10-09
  • 0
    ok many thanks for your replies2012-10-09
  • 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