CSC 321: Data Structure
Fall 2013

HW3: Algorithm Analysis

Part 1: Theoretical Analysis

  1. Using the formal definition of Big-Oh, identify and prove the Big-Oh complexity of the following cost functions:
    1. Cost(N) = 13N3 - 2N2 + 15N - 55
    2. Cost(N) = 5N log N + 2N + 1

  2. We say that a list of numbers is in non-decreasing order if every element in the list is at least as large as the one immediately before it. For example, the list [1, 4, 5, 5, 8, 10] is in non-decreasing order, whereas [2, 3, 4, 2, 5] is not. Consider the following algorithm:

    1. Compare the first number in the list with every number later in the list.
      1. If the first is > than any of these, then NO.
    2. Repeat step 1 for each number in succession (i.e., the 2nd, 3rd, ...), , comparing each with all later numbers.
    3. If no comparisons find a smaller number later in the list, then YES.

  3. Now consider an alternative algorithm for the non-decreasing problem:

    1. If the list size is odd, make it even by adding a duplicate of the last number to the end (e.g., [1, 2, 3] becomes [1, 2, 3, 3]).
    2. Compare the 1st and last numbers in the list.
      1. If the 1st is > than the last, then NO.
      2. Otherwise, repeat with the 2nd and next-to-last numbers, then the 3rd and 2nd-from-last, ..., up to the two middle numbers.
    3. If the first number in the comparison is always ≤ the second, then YES.

  4. Finally, consider the following recursive algorithm:

    1. If the list size is 0 or 1, it is sorted.
    2. Otherwise, divide the list in half.
    3. Recursively check to see if both halves are in non-decreasing order.
      1. If not, then NO.
      2. Otherwise, if the last number in the first half is > the first number in the second half, then NO.
      3. Otherwise, YES

Part 2: Experimental Analysis

For the second part of this assignment, you will develop and use a program to experimentally measure the performance of various sorting algorithms. You are given the following three files:
This class contains static methods (insertionSort, selectionSort, and mergeSort) for sorting an ArrayList of comparable items.
This class provides a simple (and simplistic) way of measuring execution time. Note that the elapsed time reported by this class is clock time, which is affected by many factors other than code execution (e.g., background jobs, garbage collection). To try to minimize these factors when using a StopWatch, you will want to limit background jobs and also perform multiple timings to identify and disregard outliers.
This driver class controls a GUI in which the user can select among the different sorting algorithms and specify the size of the list to be sorted. At the click of a button, a sort is conducted and the elapsed time is displayed.

You are to complete the project by implementing a class named SortTimer. The constructor for this class should take a string as parameter, identifying the type of sort to be timed (either "insertionSort", "selectionSort", or "mergeSort"). The only required method is timeSort, which should take a number as input and conduct the appropriate sort on a random list of that size. It should return the time it took to perform the sort (as determined by a StopWatch). Hint: to construct a random list of size N (without duplicates), first place the numbers 1 through N in the list, and then use Collections.shuffle to randomize it.

Once you have completed your class, conduct experiments to answer the following questions.