Hi,
i like to solve the attached recurrence relation, i know the homogenous solution but the problem is with the cos term.
Help is appreciated!
Mopen
I may be coming from a different field, but when we do recurrences in computer science, there needs to be some foundation from which the recurrence begins. It's important to consider the foundation in the event its contribution outweighs the rest of the recurrence.
For example, if T(n) = 3T(n/2) + n, you need to know what T(c) contributes for some small constant value (usually just described as T(0) since the value is irrelevant).
Okay. Well, then you should be able to expand out the recurrence until it's completely periodic...maybe...
$\displaystyle T(n) = 2T(n-1) - T(n-2) - (2cos(n\pi/2))/(n-1)$
$\displaystyle T(n-1) = 2T(n-2) - T(n-3) - (2cos((n-1)\pi/2))/(n-2)$
$\displaystyle T(n-2) = 2T(n-3) - T(n-4) - (2cos((n-2)\pi/2))/(n-3)$
$\displaystyle T(n-3) = 2T(n-4) - T(n-5) - (2cos((n-3)\pi/2))/(n-4)$
So:
$\displaystyle T(n) = 4T(n-2) - T(n-2) - 2T(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)$
$\displaystyle = 3T(n-2) - 2T(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)$
$\displaystyle = 6T(n-3) - 3T(n-4) - (6cos((n-2)\pi/2))/(n-3) - 2T(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)$
$\displaystyle = 4T(n-3) - 3T(n-4) - (6cos((n-2)\pi/2))/(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)$
$\displaystyle = 8T(n-4) - 4T(n-5) - (8cos((n-3)\pi/2))/(n-4) - 3T(n-4) - (6cos((n-2)\pi/2))/(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)$
$\displaystyle = 5T(n-4) - 4T(n-5) - (8cos((n-3)\pi/2))/(n-4) - (6cos((n-2)\pi/2))/(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)$
Which confirms:
$\displaystyle T(n) = - (2cos(n\pi/2))/(n-1) - (4cos(n-1\pi/2))/(n-2) - (6cos(n-2\pi/2))/(n-2) - ...$
...over lg n many terms. We can reframe T(c) as T(1), after which the summation should be:
$\displaystyle T(n) = -2 \sum_{i=1}^{n} i(cos(n-i)\pi/2))/(n-i)$
EDIT: If we assume T(0) = 0 there's no problem but otherwise you have to add an extra 3^n * T(0) (roughly speaking) to the total for the contribution of the base case, but you didn't say what the base case contribution was. It appears to be substantial, however.
I'm not good at simplification of series with transcendentals (too applied for my tastes) but I assume you can handle it here.
Hope that helps!
Wait, I made a big error. Need to recalculate, give me a moment. I'll edit this message when finished.
EDIT: Nevermind, we're good. (For a moment there I thought I hadn't handled signs properly but I was always adding at the beginning of the recurrence so it works.)
EDIT 2: Although I did make an error with the cosines at the end...just fixed. I hope it's close to correct now. Either way you should see how I did it.
EDIT 3: Sheesh. Summation should go from 1 to n, and contribution of leaves is 3^n * T(0), which is significant unless T(0) = 0. Last fix, honest.
Oh! I thought that was 2 times, not 2x.
If there's an x and an n in there, I don't know what to make of it. I guess the x is a constant and you're looking for a result that hinges on both n and x, but that's frightening.
Recurrences in CS don't even get this crazy so it's beyond my ability to solve at present, and I don't have much interest in learning. Best of luck with it, maybe someone else can assist you.