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) = 13N³ - 2N² + 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:

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

   • Does Algorithm A correctly determine whether an arbitrary number list is in non-decreasing order? If so, explain why. If not, give an example where the algorithm would return the incorrect answer.
   • What is the worst case Big-Oh complexity for this algorithm? Justify your answer.
   
   
3. Now consider an alternative algorithm for the non-decreasing problem:

   ALGORITHM B: 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]). Compare the 1st and last numbers in the list. If the 1st is > than the last, then NO. Otherwise, repeat with the 2nd and next-to-last numbers, then the 3rd and 2nd-from-last, ..., up to the two middle numbers. If the first number in the comparison is always ≤ the second, then YES.

   • Does Algorithm B correctly determine whether an arbitrary number list is in non-decreasing order? If so, explain why. If not, give an example where the algorithm would return the incorrect answer.
   • What is the worst case Big-Oh complexity for this algorithm? Justify your answer.
   
   
4. Finally, consider the following recursive algorithm:

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

   • Does Algorithm C correctly determine whether an arbitrary list is in non-decreasing order? If so, explain why. If not, give an example where the algorithm would return the incorrect answer.
   • What is the worst case Big-Oh complexity for this algorithm? Determine this by first identifying the recurrence relation that defines its cost function. Then, unwind that cost function to determine the Big-Oh complexity.

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:

Sorts.java

This class contains static methods (insertionSort, selectionSort, and mergeSort) for sorting an ArrayList of comparable items.

StopWatch.java

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.

SortGUI.java

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.

• Insertion sort and selection sort are both O(N²) algorithms. Does one tend to be faster, in absolute terms, than the other? Is it always faster, or do their relative speeds vary with list sizes? Justify your answers by providing timings for both algorithms on different list sizes.
  
  
• Theory suggests that doubling the size of the list should roughly quadruple the time for insertion and selection sorts (once the lists are big enough). Sort lists of increasing sizes and report your timings using these two algorithms. Do your timings produce the quadrupling effect? Justify your answers.
  
  
• Similarly, measure the performance of the merge sort algorithm and report your timing data. How do these timings compare in absolute terms with insertion sort and selection sort? Do your timings exhibit the rate-of-growth behavior expected of an O(N log N) sort? Justify your answers.