Solving Recurrence Equations for Algorithm Analysis

[kaalen]

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

$T(n)= 1+ \sum_{i=1}^n2(n-i+T(i))$

The Attempt at a Solution

This is how far I got:
$T(n)= 1+ \sum_{i=1}^n(2n-2i+2T(i))$
$T(n)= 1+ 2\sum_{i=1}^nn-2\sum_{i=1}^ni+2\sum_{i=1}^nT(i)$
$T(n)= 1+ 2n^2-2\frac{n(n+1)}{2}+2\sum_{i=1}^nT(i)$
$T(n)= 1+ n^2-n+2\sum_{i=1}^nT(i)$

I'm not sure what to do with that T(i) in the sum. I tried this:
$T(n)= 1+ n^2-n+2\frac{T(n)(T(n)+1)}{2}$
$T(n)= 1+ n^2-n+T(n)T(n)+T(n)$

But what do I do with that T(n)T(n)? Can it be further simplified?
Can I say $T(n)T(n)=T^2(n)$ or $T(n)T(n)=T(n^2)$

When I'm done simplifying I need to apply substitution, recursion tree or master theorem method to finish it off.

 

[susskind_leon]

Forget your approach $T(n)= 1+ n^2-n+2\frac{T(n)(T(n)+1)}{2}$ That doesn't work!
Instead, rewrite T(n) as
$$T(n) = -1 -n^2 + n - 2 \sum_{i=1}^{n-1} T(i)$$
Then start with T(1):
$$T(1) = -1 - 1^2 + 1 = -1$$
Now
$$T(2) = -1 - 2^2 + 2 - 2 * ( -1 -1^2 + 1)$$
Now
$$T(3) = -1 - 3^2 + 3 - 2 * ( -1 - 2^2 + 2 - 2 * (-1 - 1^2 + 1))$$
$$T(3) = - 1 - 3^2 + 3 + (-2) * (-1 - 2^2 + 2) + (-2)^2 * (-1 - 1^2 + 1)$$
$$T(3) = -1 + (-2) * (-1) + (-2)^2 * (-1) - 3^2 + (-2) * (-2^2) + (-2)^2 * (-1^2) + 3 + (-2) * 2 + (-2)^2 * 1$$
Do you see the pattern? For T(n), you get
$$T(n) = - \sum_{i=0}^{n-1} (-2)^i - \sum_{i=0}^{n-1} (n-i)^2 (-2)^i + \sum_{i=0}^{n-1} (n-i) (-2)^i$$
Now, all you need to do is look up the partial sums, e.g. here http://en.wikipedia.org/wiki/List_of_mathematical_series#Power_series and use you favorpite CAS software to simplify the expressions. Good luck!

 

[kaalen]

Forget your approach $T(n)= 1+ n^2-n+2\frac{T(n)(T(n)+1)}{2}$ That doesn't work!
Instead, rewrite T(n) as
$$T(n) = -1 -n^2 + n - 2 \sum_{i=1}^{n-1} T(i)$$

Hmm... haven't even thought about it this way. Mighty thanks for opening my eyes. I have since realized I had to fix my recurrence a bit because the algorithm calls itself on input from 1 to n-1, rather than to n (it would be calling itself till infinity that way).
So the corrected equation is
$$T(n) = 1 -n+ n^2 + 2 \sum_{i=1}^{n-1} T(i)$$
Few minutes ago I fed the numbers in and am now trying to figure out what the pattern is.
I noticed one thing in your proposed solution though and am hoping you can shed some more light before I proceed

How did you get from $$T(n)= 1+ n^2-n+2\sum_{i=1}^{n}T(n)$$ to
$$T(n) = -1 -n^2 + n - 2 \sum_{i=1}^{n-1} T(i)$$. Prefixes seem to have magically changed from + to - and vice versa and you seemed to have corrected $$\sum_{i=1}^{n}$$ to $$\sum_{i=1}^{n-1}$$ before I even noticed it's wrong. Just a lapsus?

 

[susskind_leon]

Firstly, it's $1+ n^2-n+2\sum_{i=1}^{n}T(i)$ and not $1+ n^2-n+2\sum_{i=1}^{n}T(n)$.
$$T(n)= 1+ n^2-n+2\sum_{i=1}^{n}T(i)= 1+ n^2-n+2\sum_{i=1}^{n-1}T(i)+2T(n)$$
Then you substract the last term and you get
$$T(n) - 2 T(n) = -T(n) = 1+ n^2-n+2\sum_{i=1}^{n}T(i)$$
Then, you multiply by -1 and you finally get
$$T(n) = -1 -n^2 + n - 2\sum_{i=1}^{n}T(i)$$
Regards!