[Solved]: Master Method to solve recurrences is 'a' related to 'b'?

Problem Detail: 

The master method allows us to solve certain recurrences of the form

$$T(n) = aT(n/b)+f(n)\,,$$

where $a\ge1$ and $b>1$ are constants and $f(n)$ is a positive function with some further restrictions that aren't important for this question.

The above recurrence describes the running time of an algorithm that divides a problem of size $n$ into $a$ subproblems, each of size $n/b$. This is intuitive in the case that $a=b$ (for example, merge sort divides the list into two parts of size $n/2$) but are there any examples of recursive algorithms that follow this schema but where $a\neq b$?

Asked By : Onkar N Mahajan

Answered By : user340082710

No it's not always the case that $a=b$, since you might not necessarily use every sub-problem. Consider for example, the binary search algorithm. In the algorithm, you have a sorted array that you break into two sub-problems of the same size ($b=2$), but only recurse on one of them ($a=1$). In this case, the recurrence would look like: $$T(n) = T(n/2) + O(1)\,.$$

For an algorithm like merge-sort however, not only is the problem broken into two sub-problems of equal size, but you recurse on both sub-problems before merging the results. In this case, you have that $a = b = 2$, and so, the recurrence looks like: $$T(n) = 2T(n/2) + O(n)\,.$$

Best Answer from StackOverflow

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