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 at 19:53
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, privacy policy and cookie policy

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