CS200 Lab 9, Divide and Conquer Recurrences

Overview

Study the Divide and Conquer Lecture notes.

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

• Monkeys.java

• 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.
• Show that the complexity of monkeys() lies between O(n squared) and O(n cubed)