Reference no: EM131662087

Question: Suppose you have a sorted array of positive and negative integers and would like to determine if there exist some value x such that both x and -x are in the array. Consider the following three algorithms:

Algorithm #1: For each element in the array, do a sequential search to see if its negative is also 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.

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 smaller than 0, advance i; if the sum is larger than 0 retreat j, and repeatedly test the sum until either x is found, or i and j meet. Determine the running times of each algorithm, and implement all three obtaining actual timing data for various values of N. Confirm your analysis with the timing data.