Let
be the running time estimate of a divide-and-conquer algorithm.
Assume that
satisfies a relation of the form:

(5)

where
is the cost of the combine-part,
is the
number of recursive calls and
is the size of a sub-problem, with
an integer
greater than
.
Assume that the following holds for all
: