1
$\begingroup$

I am trying to solve the following recurrence relation:

$T(a,b)=T(a-2^{b-1}+1,b) + T(a,b-1)$ where: $$T(a,-1)=0\\T(0,0)=0\\T(a,1)=1\\T(a,0)=1$$

I tried using Matlab and Wolfarmalpha however they don't accept recurrences with more than one variable.

Can someone give me a hint or point me in the right direction?

$\endgroup$
  • $\begingroup$ What's $l$ in the recurrence? $\endgroup$ – user58697 Mar 13 '14 at 5:58
  • $\begingroup$ sorry the $l$ is a typing error. I corrected the equation. $\endgroup$ – kyloc Mar 13 '14 at 14:18
  • $\begingroup$ Something is still wrong here. Setting $b=1$ results in $T(a,1) = T(a, 1) + 1$ $\endgroup$ – user58697 Mar 13 '14 at 17:32
  • $\begingroup$ We can assume that T(a,1)=1 $\endgroup$ – kyloc Mar 13 '14 at 22:13
  • $\begingroup$ We can never express any $T(a,2)$ as a sum of only $T(*,-1), T(*,0), T(*,1)$ values. The $b=2$ never goes away, and has no explicit definitions. You need a $b$-reducing formula. $\endgroup$ – Neil W Mar 14 '14 at 0:43
0
$\begingroup$

OK. An immediate desire is to plug in $b = 2$:

$$T(a,2) = T(a - 1, 2) + T(a, 1) = T(a-1, 2) + 1$$

so $T(a, 2) = a+1$. Next step is to plug in $b=3$:

$$T(a, 3) = T(a - 3, 3) + T(a,2) = T(a-3, 3) + (a+1) $$

Notice the arithmetic progression here. So, assuming that $T == 0$ for all negative $b$ (not just $-1$), $T(a, 3) \approx Ca^2$.

Inductively, we may conclude that $T(a, b) \approx C(b)a^{b-1}$. I have to admit that I am too lazy to estimate $C$.

I guess you can take it from here.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Just out of curiosity, which algorithm complexity you're trying to estimate? $\endgroup$ – user58697 Mar 14 '14 at 6:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.