Mathematics for Computer Science

Chapter 21 Recurrences884

Looks likepD 1 does the job. Then we compute the integral:

T.n/D‚



n



1 C

Zn

1

u 1

u^2

du



D‚



n



1 C



loguC

1

u

n

1



D‚



n



lognC

1

n



D‚.nlogn/:

The first step is integration and the second is simplification. We can drop the1=n
term in the last step, because the lognterm dominates. We’re done!
Let’s try a scary-looking recurrence:

T.n/D2T.n=2/C.8=9/T.3n=4/Cn^2 :

Here,a 1 D 2 ,b 1 D1=2,a 2 D8=9, andb 2 D3=4. So we find the valuepthat
satisfies
2
.1=2/pC.8=9/.3=4/pD1:

Equations of this form don’t always have closed-form solutions, so you may need
to approximatepnumerically sometimes. But in this case the solution is simple:
pD 2. Then we integrate:

T.n/D‚



n^2



1 C

Zn

1

u^2

u^3

du



D‚

n^2 .1Clogn/

D‚

n^2 logn

:

That was easy!

21.4.2 Two Technical Issues

Until now, we’ve swept a couple issues related to divide-and-conquer recurrences
under the rug. Let’s address those issues now.
First, the Akra-Bazzi formula makes no use of boundary conditions. To see why,
let’s go back to Merge Sort. During the plug-and-chug analysis, we found that

TnDnT 1 CnlognnC1:

This expresses thenth term as a function of the first term, whose value is specified
in a boundary condition. But notice thatTnD‚.nlogn/foreveryvalue ofT 1.
The boundary condition doesn’t matter!