Analysis of Algorithm course

Please print or write neatly

6. Design an Algorithm (30 points) You are given a sorted array A, which stores n integers, and a value key. Design an efficient divide-and-conquer algorithm that returns the index of the value key if it can be found in array A. Otherwise, the algorithm returns 0. (1) (10 points) Pseudocode (please use the textbook conventions) (2) (10 points) Analysis: Provide a tight lower and upper bound on the worst- case asymptotic running time of your pseudocode (provide the recurrence and resolve it). Justify your answer (i.e., list the cost for executing each line of code and how you calculate the total running time). (3) (10 points) Prove your answer using the substitution method