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 it. 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.

Answer rating: 100% (QA)

Run time of first algorithm is On 2 Outer loop will run for n times worst case and inner loop will a... View the full answer