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)$?
Relation between the size of sub-problems and number of sub-problems in a recurrence
algorithms;algorithm analysis;recurrence relation
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).