Algorithm Mystery(A: Array [i..j] of integer) i & j are array starting and ending indexes if...

Transcribed Image Text:

Algorithm Mystery(A: Array [i..j] of integer) i & j are array starting and ending indexes if i=j then return A[i] else k=i+floor((j-i)/2) temp1= Mystery(A[i..k]) temp2= Mystery (A[(k+1)..j] if temp1<temp2 then return temp1 else return temp2 (a) (1 points) What does the recursive algorithm above compute? (b) (4 points) Develop and state the two recurrence relations exactly (i.e., determine all constants) of this algorithm by following the steps outlined in L7-Chapter4.ppt. Determine the values of constant costs of steps using directions provided in L5-Complexity.ppt. Show details of your work if you want to get partial credit. (c) (6 points) Use the Recursion Tree Method to determine the precise mathematical expression T(n) for this algorithm. First, simplify the recurrences from part (b) by substituting the constant "e" for all constant terms. Drawing the recursion tree may help but you do not have to show the tree in your answer; instead, fill the table below. Use the examples worked out in class for guidance. Show details of your work if you want to get partial credit. x(+2)_1 You will need the following result: ** Algorithm Mystery(A: Array [i..j] of integer) i & j are array starting and ending indexes if i=j then return A[i] else k=i+floor((j-i)/2) temp1= Mystery(A[i..k]) temp2= Mystery (A[(k+1)..j] if temp1<temp2 then return temp1 else return temp2 (a) (1 points) What does the recursive algorithm above compute? (b) (4 points) Develop and state the two recurrence relations exactly (i.e., determine all constants) of this algorithm by following the steps outlined in L7-Chapter4.ppt. Determine the values of constant costs of steps using directions provided in L5-Complexity.ppt. Show details of your work if you want to get partial credit. (c) (6 points) Use the Recursion Tree Method to determine the precise mathematical expression T(n) for this algorithm. First, simplify the recurrences from part (b) by substituting the constant "e" for all constant terms. Drawing the recursion tree may help but you do not have to show the tree in your answer; instead, fill the table below. Use the examples worked out in class for guidance. Show details of your work if you want to get partial credit. x(+2)_1 You will need the following result: **

Answer rating: 100% (QA)

a b The given recursive in array A iJ j 9 find minimum value Re... View the full answer