# Solving a bivariate recurrence equation

I'm dealing with this recurrence equation:

$\qquad\displaystyle T(m, n) = T(m/2, n/2) + T(m, n/2) + O(1)$.

Any idea how to solve this? I've looked in to few advanced resources but the literature on two dimensional recurrence equation seems to be very thin.

• What about basic resources? What have you tried and where did you get stuck? (Nitpick: it's not a recurrence, but a schema that fits many. What are the anchors, what is the cost term you hide in $O(1)$?) – Raphael Aug 1 '15 at 12:34

## Repeated substitution

Repeatedly substitute in, and look for a pattern:

\begin{align*} T(m,n) &= T(m/2,n/2) + T(m, n/2) + 1\\ &= T(m/4,n/4) + 2 T(m/2,n/4) + T(m, n/4) + 3\\ &= T(m/8,n/8) + 3 T(m/4,n/8) + 3 T(m/2,n/8) + T(m, n/8) + 7\\ &\vdots\\ \end{align*}

Do you see the pattern? The coefficients $1,3,3,1$ should remind you of binomial coefficients. The pattern is

$$T(m,n) = 2^k-1 + \sum_{i=0}^k {k \choose i} T(m/2^i, n/2^k).$$

You can prove that this holds for all $k$ (by induction on $k$). Then, setting $k=\lg n$, we find

$$T(m,n) = n-1 + \sum_{i=0}^{\lg n} {\lg n \choose i} T(m/2^i, 1).$$

So it suffices to know how to evaluate $T(m,1)$ for all $m$. That information cannot be deduced from the recurrence you gave us -- it needs to be supplied as additional base cases.

For instance, suppose we are given the base cases $T(m,1) = 1$ for all $m$. Then we find

$$T(m,n) = n-1 + \sum_{i=0}^{\lg n} {\lg n \choose i} = 2n-1 = \Theta(n).$$

However, if we were given different base cases, the solution might be different.

## Guess-and-check

Another approach is to somehow guess the solution (for instance, by playing with a bunch of examples and looking for patterns), and then check that it holds. For your example, if we assume $T(m,n) = T(m/2,n/2) + T(m,n/2) + 1$ and we assume $T(m,1)=1$ for all $m$, then rubbing our rabbit's foot for luck, we might get lucky and guess

$$T(m,n) = 2n-1.$$

It is then easy to plug in and confirm that this is a valid solution to the recurrence you gave.

However, in general, guess-and-check is often very hard -- you can try many guesses, but sometimes it can be very difficult to find a guess that turns out to be correct.