Let A[1..n] be a sorted array of n integers, and x a positive integer. a) Design...

Transcribed Image Text:

Let A[1..n] be a sorted array of n integers, and x a positive integer. a) Design a O(n) recursive algorithm that returns i and / if there are two elements A[] and 40] such that ij, whose sum is exactly x, otherwise it returns none. b) Find a recurrence relation that describes the number of element comparisons carried out by the recursive algorithm. c) Solve the recurrence relation and express the solution asymptotically. Let A[1..n] be a sorted array of n integers, and x a positive integer. a) Design a O(n) recursive algorithm that returns i and / if there are two elements A[] and 40] such that ij, whose sum is exactly x, otherwise it returns none. b) Find a recurrence relation that describes the number of element comparisons carried out by the recursive algorithm. c) Solve the recurrence relation and express the solution asymptotically.

Answer rating: 100% (QA)

a To design a recursive algorithm that finds two elements Ai and Aj in the sorted array A1n such that their sum is exactly x or returns none if no suc... View the full answer