2. Consider the following divide-and-conquer algorithm to compute the po- sition a value occurs in a slice of the array A between indexes p and r inclusive. Describe informally what this algorithm does and why it solves the problem. Write down a recurrence re of this algorithm. Either find a solution to this recurrence or use the mas- ter theorem to solve this recurrence. Be sure to justify your solution. You are only required to solve the recurrence in asymptotic notatio notation). for the worst case runtime // search A[p .r] for x, returning the position i with x Ai] search (A,x,p,r) if r p then if x == A[p] then return P else return -1 if x