# Recurrence - finding asymptotic bounds for $T(n) = T(n-2) + n^2$

I've been working on a problem set for a bit now and I seem to have gotten the master method down for recurrence examples. However, I find myself having difficulties with other methods (recurrence trees, substitution). here is the question I am stuck on: $$T(n) = T(n-2) + n^2$$ Is there a pattern as follows? $$n^2 + T(n-2) + T(n-4) +...$$ where it goes until there is no more n left. so around n/2 times and would that mean that $$n^2 + (n-2)^2 + (n-i) ^2$$ so the asymptotic bound would be $\theta(n^2)$?

I am honestly taking a shot in the dark here, so I was hoping someone could help guide me in how to approach these questions.

Thank you,

Tyler

-
perhaps an indirect answer would even do, something to show how to solve questions of form t(n-i) + f(n) – Tyler Feb 5 '13 at 9:31
In addition to these answers, I would suggest searching through the site for further related problems. – Chantry Cargill Nov 5 '14 at 7:47

$$T(n) = T(n-2) + n^2 = T(n-4) + (n-2)^2 + n^2 = T(n-2k) + \sum\limits_{i = 0}^{k - 1}(n - 2i)^2$$

This goes down while $n - 2k \ge 0$. Assuming even $n$ (for asymptotic complexity, it does not really matter, and you can do similar calculations for odd $n$ also, with the same asymptotic results), we have $k = \frac{n}{2}$ at the end.

$$T(n) = T(0) + \sum\limits_{i = 0}^{\frac{n}{2} - 1}(n - 2i)^2 = \sum\limits_{i = 0}^{\frac{n}{2} - 1}(n^2 - 4ni + 4i^2) + C$$ $$T(n) = n^2\cdot\left(\frac{n}{2}-1\right) - 4n\cdot\frac{1}{2}\cdot\frac{n}{2}\cdot\left(\frac{n}{2} - 1\right) + 4\cdot\frac{1}{6}\cdot\left(\frac{n}{2} - 1\right)\cdot\frac{n}{2}\cdot(n-1) + C$$ $$\therefore \ T(n) = \Theta(n^3)$$

-

Note that if $n=2k$ is even, then $$T(n)+T(n-1) = n^2+(n-1)^2+ \cdots+4^2+3^2 + T(2)+T(1) =\frac{n(n+1)(2n+1)}{6} + C.$$ Here $C=T(2)+T(1) -2^2-1^2$ and we used the formula $\sum_{i=0}^n i^2 = \frac{n(n+1)(2n+1)}{6}$. We also note that $T(n) \sim T(n-1)$, so we may conclude that $$T(n) \sim n^3/12.$$

-

The fact that $T(n) = T(n-2) + n^2$ has the values for even and odd $n$ being completely independent suggests (at least to me) that we consider separately even and odd $n$.

For even $n$, let $R(n) = T(2n)$, so, since $T(2n) =T(2n-2)+(2n)^2$, $R(n) =R(n-1)+(2n)^2$. Therefore, $R(n) =R(0)+\sum_{k=1}^n (2k)^2 =R(0)+4\frac{n(n+1)(2n+1)}{6} \approx 4n^3/3$ so, if $n$ is even, $T(n) = R(n/2) \approx n^3/6$.

Similarly, for odd $n$, let $S(n) = T(2n+1)$ so, since $T(2n+1) =T(2n-1)+(2n+1)^2$, $S(n) =S(n-1)+(2n+1)^2$. Therefore,

$\begin{array}\\ S(n) &=S(0)+\sum_{k=1}^n (2k+1)^2\\ &=S(0)+\sum_{k=1}^n (4k^2+4k+1)\\ &=S(0)+\sum_{k=1}^n 4k^2+\sum_{k=1}^n 4k+\sum_{k=1}^n 1\\ &=S(0)+4\frac{n(n+1)(2n+1)}{6}+4\frac{n(n+1)}{2}+n\\ &\approx 4n^3/3\\ \end{array}$

so, if $n$ is odd, $T(n) = S((n-1)/2) \approx n^3/6$ again.

-

let $n=log m$ $$T(\log m)=T(\log m-\log4)+(\log m)^2$$ $$T(\log m)=T(\log m/4)+(\log m)^2$$ $$s(m)=s(m/4)+m^2$$ here $a=1,b=4$ and $f(n)=m^2$ $$m^{\log a}=1$$ $$f(m)>m^{\log a}$$ (base 4)

case (iii) of masters theorem follows hence $s(m)=\Theta(m^2)$ after comouting $c$ through $af(m/b)=cf(n)$ $$c=1/16<1$$ hence case (iii) totally followed and $s(m)=\Theta(m^2)$ and $T(m)=\Theta(2^2n)$ m not confirm about the answer but the procedure will be the same

-
See math notation guide. You can edit your answer to make it more readable. – user147263 Nov 5 '14 at 5:52