Mathematics for Computer Science

21.5. A Feel for Recurrences 889

Divide-and-conquer recurrences are also sensitive to the number of subproblems.
For example, for this generalization of the Merge Sort recurrence:

T 1 D 0

TnDaTn=2Cn1:

the Akra-Bazzi formula gives:

TnD

8

ˆ<

ˆ:

‚.n/ fora < 2

‚.nlogn/ foraD 2

‚.nloga/ fora > 2:

So the solution takes on three completely different forms asagoes from 1.99
to 2.01!
How do boundary conditions affect the solution to a recurrence? We’ve seen
that they are almost irrelevant for divide-and-conquer recurrences. For linear re-
currences, the solution is usually dominated by an exponential whose base is de-
termined by the number and size of subproblems. Boundary conditions matter
greatly only when they give the dominant term a zero coefficient, which changes
the asymptotic solution.
So now we have a rule of thumb! The performance of a recursive procedure is
usually dictated by the size and number of subproblems, rather than the amount
of work per recursive call or time spent at the base of the recursion. In particular,
if subproblems are smaller than the original by an additive factor, the solution is
most often exponential. But if the subproblems are only a fraction the size of the
original, then the solution is typically bounded by a polynomial.

Problems for Section 21.4

Homework Problems

Problem 21.1.
The running time of an algorithmAis described by the recurrenceT.n/D7T.n=2/C
n^2. A competing algorithmA^0 has a running time ofT^0 .n/DaT^0 .n=4/Cn^2. For
what values ofaisA^0 asymptotically faster thanA?

Problem 21.2.
Use the Akra-Bazzi formula to find‚./asymptotic bounds for the following divide-
and-conquer recurrences. For each recurrence,T.1/D 1 andT.n/D‚.1/for all