Homework 6

Details

The following problems are from pages 162-163 of IDMA

Problem
422
424
Problem A (below)

Problem A:
Solve the following recurrence relations. If you can provide an exact formula, do so. Otherwise, give a tight bound (not just an upper bound). Make sure you show all of your work.

1. T(n) = 2 T(n/2) + n³, T(1)=1
2. T(n) = T(n - 1) + n, T(1)=1
3. T(n) = T(n/2) + T(n/4) + T(n/8) + n², T(1)=1