CISC 3220

Assignment #4, Due: Thursday, October 6.

  1. Give a recurrence equation for the binary search algorithm. Show how to solve the recurrence equation using recursion trees.


    2. Use recursion trees to solve the following recurrences:
  2. T(n) = 4T(n/2) + n
  3. T(n) = T(n/4) + T(3n/4) + n

    4. Use the Master Theorem to solve the following recurrences:

  4. T(n) = 16T(n/4) + n^2
  5. T(n) = 3T(n/2) + 3n/4
  6. T(n) = 2T(n/4) + n