Master Theorem Form

This recurrence describes a problem that splits into a subproblems, each of size n/b, and then spends f(n) time doing the non-recursive work such as dividing the input and combining the results. It works because many divide-and-conquer algorithms build a recursion tree with the same branching pattern at each level, so the total time can be estimated by comparing the work done across all levels. The Master Theorem gives a fast way to decide whether the recursion is dominated by the branching, the combining work, or a balance between the two.

Use this form when analyzing recursive divide-and-conquer algorithms like mergesort, Karatsuba-style multiplication, or recursive search/partition algorithms where the input is split into equal-sized pieces. It is most useful when the recurrence matches exact or near-exact equal subproblem sizes and the extra work can be expressed as a simple function of n.

• Forgetting that a is the number of subproblems, not the number of recursive calls including base cases
• Using the theorem when subproblem sizes are not equal to n/b, or when the recurrence is not in the required form
• Comparing f(n) to n^(log_b a) incorrectly, especially when logarithms or lower-order terms are involved