(c) (i) The algorithm Mystery (A[0..n-1],K) is given in Appendix G. Derive a recurrence relation for...

  

Transcribed Image Text:

(c) (i) The algorithm Mystery (A[0..n-1],K) is given in Appendix G. Derive a recurrence relation for the number of times the basic operation is performed. [2 marks] (ii) Using the Master's theorem or otherwise, determine the efficiency class of algorithm Mystery. [2 marks] Appendix G: Mystery(A[0..n-1], K) //Input: An array A[0..n-1] sorted in ascending order and 11 a search key K //Output: An index of the array's element that is equal to K 11 or -1 if there is no such element 1+0; r←n-1 while / ≤r do m← [(1 + r)/2] if K = A[m] return m else if K <A[m] r←m-1 elsel m+1 return -1 (c) (i) The algorithm Mystery (A[0..n-1],K) is given in Appendix G. Derive a recurrence relation for the number of times the basic operation is performed. [2 marks] (ii) Using the Master's theorem or otherwise, determine the efficiency class of algorithm Mystery. [2 marks] Appendix G: Mystery(A[0..n-1], K) //Input: An array A[0..n-1] sorted in ascending order and 11 a search key K //Output: An index of the array's element that is equal to K 11 or -1 if there is no such element 1+0; r←n-1 while / ≤r do m← [(1 + r)/2] if K = A[m] return m else if K <A[m] r←m-1 elsel m+1 return -1

Answer rating: 100% (QA)

Based on the provided information the algorithm Mystery appears to be an implementation of the binary search algorithm The binary search algorithm is ... View the full answer