Consider the following algorithm, which recursively divides an array into two halves (call Alg2 (A[0..n-1])): ALGORITHM...

 

Transcribed Image Text:

Consider the following algorithm, which recursively divides an array into two halves (call Alg2 (A[0..n-1])): ALGORITHM Alg2 (1[left..right)) if left right return A[left] else templ Alg2 (Alleft.. (left+right)/2]]) temp2-- Alg2 (AL(left + right)/2] +1.right]) if temple temp2 return templ else return temp2 a) [5 points] What does this algorithm do? b) [15 points] Set up a recurrence relation for the algorithm's running time and solve it. Consider the following algorithm, which recursively divides an array into two halves (call Alg2 (A[0..n-1])): ALGORITHM Alg2 (1[left..right)) if left right return A[left] else templ Alg2 (Alleft.. (left+right)/2]]) temp2-- Alg2 (AL(left + right)/2] +1.right]) if temple temp2 return templ else return temp2 a) [5 points] What does this algorithm do? b) [15 points] Set up a recurrence relation for the algorithm's running time and solve it.

Answer rating: 100% (QA)

Answer a The given algorithm Alg2 is a recursive algorithm that divides an array Aleftright into two ... View the full answer