Recurrence Relation with two variables

Question

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?

Something is still wrong here. Setting $b=1$ results in $T(a,1) = T(a, 1) + 1$ — user58697, Mar 13 '14 at 17:32
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. — Neil W, Mar 14 '14 at 00:43

user58697 · Answer 1 · 2014-03-14T00:27:42.637

0

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.

edited Mar 14 '14 at 00:27

answered Mar 14 '14 at 00:19

user58697

Just out of curiosity, which algorithm complexity you're trying to estimate? – user58697 Mar 14 '14 at 06:43

1 Answers1