Homework 1 Programming Part (20 points)

The file SortAlgorithm.java contains a Java interface with 3 methods -- sortA(), sortB(), sortC() -- for sorting arrays of natural numbers, and one method -- opCount() -- that returns the number of comparison operations performed in the most recent call to one of the first three methods. The file SortAlgorithm3.class is a Java class that implements the SortAlgorithm interface. Write a well-commented and short Java program called estimate.java that will let you estimate the worst-case and average-case complexity of each of the sorting methods. We will measure the complexity as the number of comparison operations performed as a function of the size of the input array. You should present your estimates in a comment at the top of your program. They should be in the form Theta(f(n)), where f is a simple function of the input size n (e.g. "the worst-case complexity of sortB() is Theta(n^4)").

Hints:

• The file SortAlgTest.java is an example of how to use the various methods in SortAlgorithm. In particular, it uses the method createRandomArray to generate random arrays.
• Remember that Theta-notation measures how quickly the complexity grows as the input-size grows. It might be helpful to plot some data on a graph (using gnuplot, for instance).

Submission Instructions: Please submit a hard copy of your program with the findings in a comment at the top. The hard copy should be submitted at the same time as the written part of homework 1, but it should be separate with its own cover sheet.