CSE 421 Assignment #4
Winter 2006

Due: Thursday, Feb 2, 2006

Reading Assignment: Kleinberg and Tardos Chapter 6.

Problems: (see Grading Guidelines sheet before answering)

1. Suppose T(n) = 8T(n/2) + n², and T(1) = 0. Prove that T(n) = O(n³). You may assume that n is a power of 2.

2. Suppose T(n) = 7T(n/2) + n², and T(1) = 0. Show that T(n) = O(n^lg(7)). You may assume that n is a power of 2.

3. Give the best asymptotic upper bound you can for T(n) in each of the following examples. You may assume T(n) is constant for n <= 2.
   1. T(n) = 5T(n/3) + n.
   2. T(n) = T(2n/3) + n.

4. Kleinberg and Tardos, Chapter 5, Problems 2 and 3.

5. Extra credit: Kleinberg and Tardos, Chapter 5, Problem 5.pwd