CS200 Lab 8, Divide and Conquer Recurrences
Overview
Study the Divide and Conquer Lecture notes.
Take the following code and put it in an Eclipse project:
- Run the code, experiment with it. What does a call m.monkeys() do? Can you convince yourself of this?
- Write a recurrence relation for the complexity of this code, in terms of number of method calls.
- Solve the recurrence using the Master Method. You have to bend the rules a little... How?
- Show that the complexity of monkeys() lies between O(n squared) and O(n cubed)