Relation between the size of sub-problems and number of sub-problems in a recurrence

Question

Below is a well-known equation for generalized recurrence relation in a divide and conquer paradigm (as described in CLRS) --

$$T(n) = aT(n/b) + f(n), \quad \text{where} \quad a \gt 1 \text{ , } b \geq 1$$

If we consider a case for merge-sort, the relation will look like this --

$$T(n) = 2T(n/2) + \Theta(n) \qquad \qquad (i)$$

which is quite straight-forward, i.e. we have $2$ sub-problems of size $n/2$ each, ($1/2$ of the original sub-problem), and $\Theta(n)$ operations to merge them.

Now if we have a relation like --

$$T(n) = 3T(n/2) + \Theta(n) \qquad \qquad (ii)$$

then we can assume that there are $3$ "overlapping" sub-problems, as each of them with size $n/2$. Let's consider again --

$$T(n) = 2T(n/4) + \Theta(n) \qquad \qquad (iii)$$

now, what does it mean? Are there $2$ sub-problems with size $n/4$? How is it possible? If we divide the whole problem into $4$ equal sizes then we should need something like $4T(n/4)$ instead of $2T(n/4)$ to balance the recurrence tree (each node with 4 leaves), right? Is this relation realistic?

If this is the case, then why there is no constraint like $b < a$ ? Moreover, is there any algorithm that follows the recurrence as in $(ii)$ and $(iii)$?

Answer 1

A simple, specific example of an algorithm with a type $(iii)$ recurrence is binary search. At each point you decide whether to look in the left or the right half of the current section of the array, so your problem halves, and you only have one subproblem. The recurrence is then $T(n) = T(\frac{n}{2}) + O(1)$.

So you might get a type $(iii)$ any time you "discard" part of the input at each step.

A divide and conquer approach to multiplying large numbers can give you a type $(ii)$ recurrence (obviously there's faster algorithms now though). If you split the numbers in half, you can turn one multiplication of two large numbers in to four multiplications of half-sized numbers, plus some addition. Gauss reduced this to three multiplications of half size numbers (but with more addition and subtraction), so the recurrence for this algorithm is $T(n) = 3T(\frac{n}{2})+O(add)$ (the exact recurrence depends on how you deal with addition/subtraction).

Answer 2

One of the wonderful examples that "discard" some sub-problems is the "VLSI Layout Problem". You can find this example in this MIT OCW Lecture (from 55m:30s). I summarize it here.

The problem is to embed a complete binary tree $T$ with $n$ leaves (it is circuit) into a grid (no crossing edges) with minimum area. For simplicity, we assume the height of $T$ is even.

A so-called $H$-layout (wiki) gives us an $O(n)$ solution. The following figure shows an example of $T$ of height 4.

The key point here is although we divide the origin problem into 4 sub-problems, either for the width $W(n)$ or the height $H(n)$ of the rectangle area, only two sub-problems count.

In terms of recurrence, we have $$W(n) = H(n) = 2T(n/4) + O(1) = O(\sqrt{n}).$$