CS200 Lab 8, Divide and Conquer Recurrences

Overview

Study the Divide and Conquer Lecture notes.

Code

Take the following code and put it in an Eclipse project:

• Monkeys.java

Procedure

• Run the code, experiment with it. What does the 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²) and O(n³).