Assignment 1: due 3/8 in class
Reading assignment Chapter 4
Problems to be handed in:
Argue that the solution to the recurrence T(n)=T(n/3)+T(2n/3)+cn,
c is a constant, is &Omega (nlg n) by appealing to a recursion tree.
- Use the master method to solve the following
a. T(n)=3T(n/4)+ n^(1/2)
- 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.