Homework 7 (assigned August 2, due August 9)

1. Suppose that T(n) = 2T(n/2) + 3 when n is even and T(1) = 5. Find

   (a) T(2)   (2 points)

   (b) T(8)   (2 points)

   (c) T(64)  (3 points)

2. Use iteration to solve each of the following recurrences. Show all important steps. (10 points each)

   (a) T(n) = T(n - 1) + 3, with T(1) = 2.

   (b) T(n) = 3T(n/2) + 1, with T(1) = 1.   Use the fact that a^log_bn = n^log_ba and state your answer as a function of n.
   (You may assume that n is a power of 2, i.e., n = 2^k for some k.)

   (c) T(n) = T(n/3) + 1, with T(1) = 1.
   (You may assume that n is a power of 3, i.e., n = 3^k for some k.)

3. A person deposits $1000 in an account that yields 5% interest compounded yearly.

   (a) Set up a recurrence for the amount in the account at the end of n years. (3 points)

   (b) Find an explicit formula for the amount in the account at the end of n years. Your answer should be a function of n. (3 points)

   (c) How much money will the account contain after 10 years? (2 points)

4. Prove that T(n) = 2T(n/2) + 2 solves to T(n) = 2n - 2.   (5 points)
   (You may assume that n is a power of 2.)

5. Prove that T(n) = 2T(n/2) + n solves to T(n) = nlgn + n.   (5 points)
   (You may assume that n is a power of 2.)

Gerry Brady
Tuesday August 2 23:39:38 CDT 2005