Bill Teter
Office:          149 Redcay
Telephone:    2782
Office Hours:  Tuesday, Thursday 9:00-12:00

email:  william.teter@plattsburgh.edu

Lab 6  -- lab based complexity analysis

In this lab you will generate data that should confirm the worst case complexity of the binary search algorithm for finding a component of a sorted array is log n.

You will use methods from the Arrays class both for searching an array and for sorting an array.  The Random class will be used for generating numbers in a pseudo random order.  You will also create a class called MyInteger which implements the Comparable interface and which will, in a clever way, keep track of how many times the compareTo() method executes while trying to locate a component in a sorted array.  We will not use a clock to measure complexity.  Instead we will take the number of invocations of compareTo() as a measure of the number of statements that must execute when the binary search algorithm runs.

From the definition of big theta, we know that if f(n) is big theta(g(n)) then the values of f(n)/g(n) as n gets large should not approach infinity nor should they approach zero.  Instead the values should  be restricted to a fixed interval [a, b] of positive numbers.

Plan:

The main method should do the following loop for n = 10, 100, 1000, 10000, 100000
        create an array of MyInteger objects of size n filled with random integers
        sort the array
        set the compareTo counter to zero
        use binary search algorithm to look for a number that isn't there, which is the worst case
        retrieve the number of times compareTo() was called and call this number f(n)
        print f(n) / log n  (make sure this computation is done as doubles.)

The output should be a sequence of numbers converging to a positive constant.
 

The Arrays class contains several utilities (class methods) for managing arrays.  You will be using the binary search and sort method.  More precisely, you will use the binarySearch(Object[] a, Object k)  and sort(Object[] a) methods.  Each require that the array contain objects that are Comparable.  The Comparable<T> interface contains just one method int compareTo(T other) which has the behavior:  this.compareTo(other) returns a negative if this is less than other, zero if this is equal to other and a positive int if this is greater than other.

The MyInteger class will implement Comparable<MyInteger> interface.  One field will hold the int value of an object.  And, It will need a static field to count the number of times the compareTo method is invoked by the binary search method.  There should be a constructor with an int parameter to create a MyInteger object.  the class should have two static methods, one to access the static count field, and another to reset it to zero.