Assignment 1: due 3/8 in class

Reading assignment Chapter 4

Problems to be handed in:

1. Argue that the solution to the recurrence T(n)=T(n/3)+T(2n/3)+cn,
   where c is a constant, is &Omega (nlg n) by appealing to a recursion tree.
2. Use the master method to solve the following recurrences.
   a. T(n)=3T(n/4)+ n^(1/2)
   b. T(n)=2T(n/4)+n.
   c. T(n)=7T(n/3)+n^2
   d. T(n)=7T(n/2)+n^2
   
3. Solve the following recurrences:
   a. T(n)=4T(n/3)+nlg n.
   b. T(n)=T(n-2) + n^2
   c. T(n)=T(n-1)+ lg n.