Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

up vote 6 down vote accepted

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)\,.$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.