1
$\begingroup$

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)$?

$\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$
    – gnasher729
    Oct 16, 2021 at 19:53

1 Answer 1

1
$\begingroup$

$$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.