master-theorem case 3

Now flip the balance the other way. Suppose the divide-and-combine work at the top of the recursion is so heavy that it outweighs everything the recursive calls do beneath it. Then the very first level — the root — accounts for almost all the running time. Case 3 is when the root wins.

Case 3 applies when f(n) = Omega(n^(log_b a + epsilon)) for some epsilon > 0 (the combine work is polynomially LARGER than the critical term) AND f satisfies the regularity condition a f(n/b) <= c f(n) for some constant c < 1 and large n. When both hold, T(n) = Theta(f(n)). The tree intuition: per-level totals shrink geometrically as you go down (the root's f(n) dwarfs the children's combined a f(n/b)), so summing the geometric series the root's term dominates and the total is just Theta(f(n)). The regularity condition is what guarantees that geometric shrink — without it, the levels could fail to decay and the simple conclusion would break.

This case covers recurrences where the heavy lifting is the combine, not the recursion — for instance T(n) = 2 T(n/2) + n^2, where log_2 2 = 1 and f(n) = n^2 is larger by a factor of n, giving T(n) = Theta(n^2). The honest subtlety is the regularity condition: for ordinary polynomial f it always holds, but for unusual f (oscillating or with sharp factors) it can fail, and then Case 3 does not apply even though f is polynomially larger. Always check it, even if it usually passes silently.