Completing the Program

This program prints a table of runtimes (these are displayed in seconds) for given functions on arrays. The program tests different array sizes to establish a relationship between input size and runtime. It tests each array size multiple times and then takes an average of the times. Here are example calls to the timing functions:

int[] sizes1= { 1000, 2000, 4000, 8000, 16000};

fRT = timeAlgorithm("Insertion Sort", 10, 5, sizes1, "insertionSortInitial" ); printRuntimeTable(fRT);

fRT = timeAlgorithm("quicksort", 10, 5, sizes1, "quickSortOptInitial" ); printRuntimeTable(fRT);

This results in following table:

Note your runtimes may vary since the test data is randomly generated.

The runtimes are stored in a functionRuntimes class. You are completing a program to create and fill data in this class, print the data of this class.

You are given a partial implementation in the files “MysteryRuntime.java”, “functionRuntimes.java”, and “ArrayAlgs.java”. The portions of code that you need to write have been marked with the text “TODO”.

Using the Program

After you have the program completed, you should use it to help determine the asymptotic runtimes of the three mystery functions (i.e., mysteryRuntime1, mysteryRuntime2, mysteryRuntime3).

Be sure to also examine the code of the mystery functions to confirm your estimations.

Fill in the following table with your runtimes:

/*

Give your asymptotic estimates for the runtimes of the following 3 functions:

mysteryRuntime1: O( )

mysteryRuntime2: O( )

mysteryRuntime3: O( )

*/

1. Longest Sorted Subarray

Consider the following problem:

Input: An array A[1 . . . n] of integers

Output: The largest integer m such that the array A[1 . . . n] has subarray of length m which is in sorted order (i.e, increasing order).

The following pseudocode finds the length of the longest of the given array A[1 . . . n] by considering all possible subarrays:

The following code checks if an array is increasing (i.e., each number is smaller than the next in the array).

Example: longestSubArray( [2, 4, 3, 8, 5, 6, 7, 9, 0, 1] ) returns 4

(1) Consider running longestSubArray on the array:

[119, 100, 112, 114, 125, 113, 110, 129, 130, 140, 142, 115, 120]

What does longestSubArray return and what is the longest sorted subarray of A?

(2) Give the best-case runtime of longestSubArray in asymptotic (i.e., O) notation as well as a description of an array which would cause this behavior.

(3) Give the worst-case runtime of longestSubArray in asymptotic (i.e., O) notation as well as a description of an array which would cause this behavior.

(4) Is this an efficient algorithm for finding the longest sorted subarray? Can you find a better algorithm for computing this?

2. Asymptotic Notation (4 points)

Show the following using the definitions of O, Ω, and Θ.

(1) 2n 3 + n 2 + 4 ∈ Θ(n 3 )

(2) 3n 4 − 9n 2 + 4n ∈ Θ(n 4 )

(Hint: careful with the negative number)