Implement three different algorithms that solve the same problem, compare their running times experimentally, and analyze them asymptotically.

Problem Statement

Suppose you have a sorted array of integers and would like to determine if there exists an element x, such that x and -x are both in the array. For example:

For the array <-4, -2, 1, 3, 5, 7, 9>, the algorithm returns false, because there is no element whose negative is in the array

For the array <-4, -2, 1, 2, 3, 5, 7, 9> then the algorithm returns true, since 2 and -2 are both in the array

Algorithms

Here are three different algorithms which solve the preceding problem:

Algorithm #1: For each element in the array, do a sequential search to see if its negative is also in the array. Sequential search means you examine each element in the array one by one (iterate over the elements in the array).

Algorithm #2: For each element in the array, do a binary search to see if its negative is also in the array. Pseudocode for binary search algorithm:

input: x (value we are searching for) first = 0 last = arraySize while first < last do middle = (first + last)/2 if array[middle] == x return true else if x < array[middle] last = middle else first = middle + 1 end return false;

Algorithm #3: Maintain two indices i and j, initialized to the first and last element in the array, respectively. If the two elements being indexed sum to 0, then x has been found. Otherwise, if the sum is less than 0, increment i; if the sum is greater than 0 then decrement j. Repeatedly test the sum until either x is found or i and j meet.

What To Do

Implement each of the three algorithms. You should implement these algorithms exactly as described; there is no need to try and improve or change them.

Analyze the three algorithms asymptotically, by finding a Big-Oh function for the worst-case running time in terms of n, the length of the array

Confirm your analysis in step 2 by timing the algorithms for different input sizes. At a minimum, you should use input sizes of: 25k, 50k, 100k, 200k, and 400k. Present this data in a table.

Code Structure

Your project should have two classes: Search and Driver.

The Search class should have three static methods; one method for each algorithm. Each method should take a sorted array of ints as a parameter and return a boolean. You may create private helper methods as needed.

The Driver class should have a main method, which contains your timing code. Your timing code should time each algorithm with random arrays with n integers.

NOTE: If the pair of ints is found quickly, your algorithm might appear faster than the average case. Run your algorithm with several different arrays of data to verify your data.

Hints on Creating Test Cases

To make a random test case, you should:

Fill an array with random numbers

Use Arrays.sort() to sort the array

If you want test cases that return false, use a large range of random numbers in step 1.

If you want test cases that return true, use a small range of random numbers in step 1.