[Solved]: Relation between the size of sub-problems and number of sub-problems in a recurrence

Problem Detail: 

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)$?

Asked By : ramgorur

Answered By : Luke Mathieson

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13234

 Ask a Question

 Download Related Notes/Documents