This is a review question and the teachers gave us the answer as $n^2$. Can someone explain why it is $n^2$?
Thank you
Asked
Active
Viewed 473 times
2
-
We have $$ \sum_{i=0}^{n-1}2i+1=n^2. $$ I believe you can modify this to solve your problem. – Ian Coley Mar 21 '14 at 22:17
-
See Faulhaber's formulas, and note that $\displaystyle\sum_0^n(3k+1)=3\sum_0^nk+\sum_0^n1=3\cdot S_n+(n+1)$. – Lucian Mar 21 '14 at 22:46
3 Answers
4
It is a sum of $n$ terms, each bounded by $4 n$, so bounded by $n \cdot 4 n = O(n^2)$.
(Yes, this is much less detailed than the other answers; but it also has the virtue that it doesn't require to get anywhere near the precise sum.)
vonbrand
- 27,812
3
If $$g(n)=0+1+2+\cdots +n= \dfrac{n(n+1)}{2}$$ then $$f(n)=3g(n)+ (n+1) = \dfrac{(3n+2)(n+1)}{2}$$ which is $O(n^2)$.
Henry
- 157,058
1
$$ s_n=1+4+7+\cdots+(3n+1)=\frac{3n^2+5n+2}{2}={\mathcal O}(n^2), $$ since $$ \frac{s_n}{n^2} $$ is bounded, and in particular, $$ \frac{3}{2}\le \frac{s_n}{n^2}\le 5. $$
Yiorgos S. Smyrlis
- 83,933