1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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)$?) $\endgroup$ – Raphael Aug 1 '15 at 12:34
5
$\begingroup$

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.

$\endgroup$

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.