master-theorem case 2

Some divide-and-conquer algorithms feel perfectly balanced: every level of the recursion tree does about the same total amount of work. Merge sort is the classic example — splitting, then merging, costs Theta(n) at the top, and the merges at every depth also add up to Theta(n). Case 2 is exactly this balanced situation, and it is where the famous extra log n factor comes from.

Case 2 applies when f(n) = Theta(n^(log_b a)) — the combine cost matches the critical term exactly. Then T(n) = Theta(n^(log_b a) log n). Why the log? Through the tree: every level totals Theta(n^(log_b a)) (the per-level work neither grows nor shrinks as you descend), and there are Theta(log n) levels because the size shrinks by the factor b each step until it reaches the base case. Multiply the per-level work by the number of levels and you get the n^(log_b a) log n result. For merge sort, log_2 2 = 1, f(n) = n = Theta(n^1), so T(n) = Theta(n log n).

This case shows up whenever the per-level work is flat, and it explains why O(n log n) is so common for good divide-and-conquer sorts and similar algorithms. There is a more general version of Case 2 that allows f(n) = Theta(n^(log_b a) log^k n) for k >= 0, yielding T(n) = Theta(n^(log_b a) log^(k+1) n) — each existing log raises the power of the final log by one. The honest caveat: f(n) must match n^(log_b a) up to a constant (or such a log power); if it differs by a genuine power of n you are in Case 1 or 3, not here.