- #1
kaalen
- 20
- 0
Homework Statement
I need to solve a recurrence equation in order to perform algorithm analysis. I got the recurrence from the algorithm I developed. It's been years since I did my undergrad degree and my maths is rusty.
Homework Equations
[itex]T(n)= 1+ \sum_{i=1}^n2(n-i+T(i)) [/itex]
The Attempt at a Solution
This is how far I got:
[itex]T(n)= 1+ \sum_{i=1}^n(2n-2i+2T(i)) [/itex]
[itex]T(n)= 1+ 2\sum_{i=1}^nn-2\sum_{i=1}^ni+2\sum_{i=1}^nT(i) [/itex]
[itex]T(n)= 1+ 2n^2-2\frac{n(n+1)}{2}+2\sum_{i=1}^nT(i) [/itex]
[itex]T(n)= 1+ n^2-n+2\sum_{i=1}^nT(i) [/itex]
I'm not sure what to do with that T(i) in the sum. I tried this:
[itex]T(n)= 1+ n^2-n+2\frac{T(n)(T(n)+1)}{2} [/itex]
[itex]T(n)= 1+ n^2-n+T(n)T(n)+T(n) [/itex]
But what do I do with that T(n)T(n)? Can it be further simplified?
Can I say [itex]T(n)T(n)=T^2(n)[/itex] or [itex]T(n)T(n)=T(n^2)[/itex]
When I'm done simplifying I need to apply substitution, recursion tree or master theorem method to finish it off.