The master theorem uses asymptotic notation to give bounds for divide-and-conquer algorithm recurrences of the form
 |
(1)
|
with 
and 
.
Write 
.
In its standard form, the theorem gives
 |
(2)
|
The regularity condition in the third case requires 
for some 
and all sufficiently large 
, meaning for every 
beyond some fixed threshold. The condition ensures that the
nonrecursive work decreases geometrically from one recursion level to the next. In
the cases above, 
is big-O notation for an asymptotic upper bound,
is big-omega
notation for an asymptotic lower bound, and 
is big-theta notation
for a matching upper and lower bound. Recurrences falling between these cases require
other methods.
