I'm trying to solve this recurrence. I applied the iterative method: $$T(n) = T(n-2)+n^2$$ $$=T(n-4)+(n-2)^2+n^2$$ $$=T(n-6)+(n-4)^2+(n-2)^2+n^2$$ $$\cdot$$$$\cdot$$$$\cdot$$ $$=T(n-2k) + \sum_{i=0}^{k-1}(n-2i)^2$$ So $n-2k=1$ when $n=2k+1$ and we have: $$\sum_{i=0}^{(n-3)/2}(n-2i)^2$$ Now how can I demonstrate that this series is $\Theta(n^3)$?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ How many numbers >= n^2/4 are you adding at least? And him many numbers <= n^2 are you adding? That’s gives you a simple lower and upper bound. zkutch’s formula gives you a much better result, but this answers the question with only trivial maths. $\endgroup$– gnasher729Oct 16, 2021 at 19:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
$$\sum_\limits{i=0}^{(n-3)/2}(n-2i)^2 = \sum_\limits{i=0}^{(n-3)/2}(n^2-4in+4i^2)=\\ =n^2\frac{n-3}{2}-4n\frac{\frac{n-3}{2}\left(\frac{n-3}{2}+1\right)}{2}+4\frac{\frac{n-3}{2}\left(\frac{n-3}{2}+1\right)\left(2\frac{n-3}{2}+1\right)}{6}=n^3\cdot A_n$$ Where is easy to see, that $A_n$ is bounded.
