Question

The following algorithm (Rosen pg. 363) is a recursive version of linear search, which has access to a global list of distinct integers a_1, a_2,..., a_n. procedure search(i, j, x : i,j, x integers, 1 < i < j < n) if a_i = x then return i else if i = j then 4. return 0 else return search(i + 1, j, x) Prove that this algorithm correctly solves the searching problem when called with parameters i = 1 and j = n. That is, prove that it returns the location of the target value x in the list, and returns 0 if the target is not present in the list. Let T(n) be the running time of this algorithm. Write a recurrence relation that T(n) satisfies. Solve the recurrence found in part (b) and write the solution in Theta notation.