1
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.