4. (5 points) The following algorithm has access to a global list of distinct integers a1,a2,. , an. When called with parameters i,j, x, Search(i.,j, x) returns the location of the target value z among {aiaj, or 0 if the target value is not present in fai...aj) procedure Search(i, j, z : i integers, 1 i j n) 1. if air then 2.return i 3. else if i -j then return 0 5. else 6. return Search(i +1.j, r) Let T(n) be the running time of this algorithm. Write a recurrence relation that T(n) satisfies. Then solve the recurrence and write the solution in notation. 4. (5 points) The following algorithm has access to a global list of distinct integers a1,a2,. , an. When called with parameters i,j, x, Search(i.,j, x) returns the location of the target value z among {aiaj, or 0 if the target value is not present in fai...aj) procedure Search(i, j, z : i integers, 1 i j n) 1. if air then 2.return i 3. else if i -j then return 0 5. else 6. return Search(i +1.j, r) Let T(n) be the running time of this algorithm. Write a recurrence relation that T(n) satisfies. Then solve the recurrence and write the solution in notation