master-theorem case 1

Picture the recursion tree of T(n) = a T(n/b) + f(n). If the work piles up faster as you go down toward the many leaves than the combine step can keep up with, the bottom of the tree carries almost all the cost. Case 1 is the situation where the leaves win.

Formally, Case 1 applies when f(n) = O(n^(log_b a - epsilon)) for some constant epsilon > 0 — that is, the combine work is polynomially SMALLER than the critical term n^(log_b a). When this holds, T(n) = Theta(n^(log_b a)). The intuition via the tree: there are a^(log_b n) = n^(log_b a) leaves, each doing Theta(1) work, so the leaves alone contribute Theta(n^(log_b a)); and because each higher level does geometrically less, the whole tree is dominated by that leaf total. The key word is epsilon: f must be smaller by an actual power of n, not merely by a logarithm.

This is the case for recurrences where you make many subproblems and the combine is cheap. Strassen's algorithm, T(n) = 7 T(n/2) + Theta(n^2), has log_2 7 ≈ 2.807, and n^2 = O(n^(2.807 - epsilon)), so Case 1 gives Theta(n^(log_2 7)) ≈ Theta(n^2.81) — faster than the naive Theta(n^3). The honest caveat: you must verify the gap is polynomial. If f(n) were n^(log_b a) / log n, it is smaller than the critical term but not by a power of n, so Case 1 does NOT apply and you are in a gap.