Mathematics for Computer Science

21.5. A Feel for Recurrences 891

The final, merged list is the output. What’s great is that because multiple copies
of each number are maintained, even if the sorter occasionally forgets about a num-
ber,OverSortcan still output a complete, sorted list.

(a)LetT.n/be the maximum number of comparisons thatOverSortcould use
to sort a list ofndistinct numbers, assuming the sorter never forgets a number and
nis a power of 3. What isT.3/? Write a recurrence relation forT.n/. (Hint:
Merging a list ofjdistinct numbers and a list ofkdistinct numbers, and throwing
out duplicates of numbers that appear in both lists, requiresjCkdcomparisons,
whend > 0is the number of duplicates.)

(b)Now we’re going to apply the Akra-Bazzi Theorem to find a‚bound on
T.n/. Begin by identifying the following constants and functions in the Akra-Bazzi
recurrence (21.4):

The constantk.

The constantsai.

The constantsbi.

The functionshi.

The functiong.

The constantp. You can leavepin terms of logarithms, but you’ll need a

rough estimate of its value later on.

(c)Does the conditionjg^0 .x/jDO.xc/for somec 2 Nhold?

(d)Does the conditionjhi.x/jDO.x=log^2 x/hold?

(e)Determine a‚bound onT.n/by integration.

Exam Problems

Problem 21.4.
Use the Akra-Bazzi formula to find‚./asymptotic bounds for the following recur-
rences. For each recurrenceT.0/D 1 andn 2 N.

(a)T.n/D2T.bn=4c/CT.bn=3c/Cn

(b)T.n/D4T



n=2C

p

n

̆

Cn^2

(c)A society of devil-worshipers meets every week in a catacomb to initiate new
members. Members who have been in the society for two or more weeks initiate
four new members each and members who have been in the society for only one