Master Theorem Case 2 (balanced recurrence, the merge-sort case)

The Master Theorem

Many divide-and-conquer algorithms split a problem of size $n$ into $a$ subproblems of size $n/b$, then spend $f(n)$ extra work splitting and combining. This gives the recurrence

$T(n) = a\,T\!\left(\frac{n}{b}\right) + f(n), \qquad a \ge 1,\; b > 1.$

The outcome is decided by comparing $f(n)$ against the watershed function $n^{\log_b a}$ — the total cost of the leaves of the recursion tree.

Case 2 — the balanced case

Case 2. If $f(n)=\Theta\!\left(n^{\log_b a}\right)$, then $T(n)=\Theta\!\left(n^{\log_b a}\log n\right)$.

Intuition from the recursion tree: at depth $i$ there are $a^{i}$ nodes, each doing $f(n/b^{i})$ work. When $f(n)=\Theta\!\left(n^{\log_b a}\right)$, every level does the same total amount of work, $\Theta\!\left(n^{\log_b a}\right)$. The tree has height $\log_b n=\Theta(\log n)$, so summing identical work over all levels multiplies by a $\log n$ factor:

$T(n)=\underbrace{\Theta\!\left(n^{\log_b a}\right)}_{\text{per level}}\times\underbrace{\Theta(\log n)}_{\text{levels}}=\Theta\!\left(n^{\log_b a}\log n\right).$

The extra $\log n$ is the signature of Case 2 — it is what separates it from Cases 1 and 3, where one end of the tree dominates and no log appears.

How to apply (recipe)

1. Read off $a$ (number of recursive calls), $b$ (shrink factor), and $f(n)$ (non-recursive work per call).
2. Compute the watershed exponent $\log_b a$ and form $n^{\log_b a}$.
3. Compare $f(n)$ to $n^{\log_b a}$. If they are the same order ($\Theta$ of each other), you are in Case 2.
4. Answer: $\Theta\!\left(n^{\log_b a}\log n\right)$.

Mini-example — merge sort and friends

Merge sort: $T(n)=2T(n/2)+\Theta(n)$. Here $a=2$, $b=2$, so $n^{\log_2 2}=n^{1}=n$. Since $f(n)=\Theta(n)$ matches, Case 2 gives the famous

$T(n)=\Theta(n\log n).$

The konkur question with f2(n) = f2(n/2) + f1(n) + f2(n/2) is exactly this shape: two half-size calls plus $\Theta(n)$ work from f1, i.e. $T(n)=2T(n/2)+\Theta(n)\Rightarrow\Theta(n\log n)$.

Binary search of a different flavor: $T(n)=2T(n/2)+\Theta(1)$ is not Case 2 — here $f(n)=\Theta(1)$ but $n^{\log_2 2}=n$, so leaves dominate (Case 1) and $T(n)=\Theta(n)$. Matching $f(n)$ to $n^{\log_b a}$ is the whole game.

Exam trick: Case 2 is the only case that produces a $\log n$ factor. The instant you see two half-size calls plus linear work — $2T(n/2)+\Theta(n)$ — answer $\Theta(n\log n)$ on sight. Do not be fooled when the linear term is hidden inside a helper function (like an $O(n)$ loop): it still counts as $f(n)=\Theta(n)$.