retagged by
297 views
3 votes
3 votes

Let $T(n)$ be
$$
T(n)=T(n-1)+n^{2} $$$$
T(1) = 1
$$
What will be asymptotic bound on $T(n) ?$

  1. $\Theta\left(\mathrm{n}^ 2\right)$
  2. $\Theta\left(n^ 3\right)$
  3. $\Theta\left(n^ 4\right)$
  4. $\Theta\left(n^ 2 \log n\right)$
retagged by

1 Answer

1 votes
1 votes
$$
\begin{aligned}
T(n) &=T(n-2)+(n-1)^{2}+n^{2} \\
&=T(n-3)+(n-2)^{2}+(n-1)^{2}+n^{2} \\
&=T(n-4)+(n-3)^{2}+(n-2)^{2}+(n-1)^{2}+n^{2} \\
T(n) &=T(0)+1^{2}+2^{2}+3^{2}+\cdots+n^{2} \\
1^{2}+2^{2}+\cdots+n^{2}=\frac{n(n+1)(2 n+1)}{6}
\end{aligned}
$$
so
$$
T(n)=T(0)+\frac{n(n+1)(2 n+1)}{6}
$$
so we conclude that $T(n)=O\left(n^{3}\right)$, in asymptotic notation.
Answer:

Related questions

3 votes
3 votes
1 answer
1