Homework #2
COSC 5110
Analysis of Algorithms
1. Exercise 2.23.
2. Let
T(n) = T(an) + T(bn) + cn,
where 1 > a ≥ b > 0 and c > 0 are constants.
(a) Prove that the total work performed across the k
th level of the recursion tree is at most
c(a + b)
kn, for every k ≥ 0.
(b) For which values of k is the total work performed across the k
th level of the recursion
tree equal to c(a + b)
kn?
(c) What is the depth of the recursion tree?
(d) Solve for T(n) in each of the following cases:
i. a + b < 1.
ii. a + b = 1.
iii. a + b > 1.
3. The median-of-medians algorithm we covered in class begins by dividing the array into blocks
of 5. What happen if we modify the algorithm to use a different block size? Bound the
number of comparisons in each of the following cases. (You may use your results from the
previous problem.)
(a) Block size 3.
(b) Block size 5.
(c) Block size 7.
(d) Block size 9.
(e) Extra credit: Block size 2k + 1, for a general k ≥ 1.
(f) Compare your above results [(a)-(d), or (a)-(e) if you did (e)] and determine which block
size minimizes the number of comparisons.
1
