# Solving complicated recurrence

This question is based on the solution to topcoder SRM-620 question:

bool solve(int a, int b, int c, int d)
{
if(a == c && b == d)
return true;
if(a > c || b > d)
return false;
return solve(a+b,b,c,d)||solve(a,b+a,c,d);
}


The time complexity is given by the recurrence formula

$$T(a,b,c,d) = \begin{cases} c_1, & \text{a=c and b=d}, \\ c_2, & \text{a>c or b>d}, \\ T(a+b,b,c,d) + T(a,b+a,c,d) +c_3, & \text{otherwise.} \end{cases}$$

How do I transform this to closed form if possible?

• I suggest that you run your algorithm the other way around - subtract c from d or vice versa. – Karolis Juodelė May 11 '14 at 6:52
• Do you want a closed form or just an estimate? – Yuval Filmus May 12 '14 at 1:12
• What have you tried and where did you get stuck? Note that in your algorithm, solve does sometimes take four and sometimes two parameters. – Raphael May 12 '14 at 8:22
• @Raphael I want to analysis the complexity of it, but stuck at the transform the recurrence formula to closed form – 张 源 May 13 '14 at 5:06
• @YuvalFilmus if a closed form is not possible, an estimate is ok – 张 源 May 13 '14 at 5:07