(20 points) Let A[1..n] be an array of numbers. To find the largest number in A,...

   

Transcribed Image Text:

(20 points) Let A[1..n] be an array of numbers. To find the largest number in A, one way is to divide A into two halves, recursively find the largest number in each half, and pick the maximum between the two. (a) (15 points) Write a recursive algorithm to implement the above scheme. Write a recurrence relation describing the running time of the algorithm and solve it to give a tight bound on the running time of this algorithm. (b) (5 points) Does this recursive algorithm perform better than an incremental algorithm that computes the largest element in A by iterating through the elements of A? Explain. (20 points) Let A[1..n] be an array of numbers. To find the largest number in A, one way is to divide A into two halves, recursively find the largest number in each half, and pick the maximum between the two. (a) (15 points) Write a recursive algorithm to implement the above scheme. Write a recurrence relation describing the running time of the algorithm and solve it to give a tight bound on the running time of this algorithm. (b) (5 points) Does this recursive algorithm perform better than an incremental algorithm that computes the largest element in A by iterating through the elements of A? Explain.