a) Execute interpolation search for the key k=120 in the following array: [0,1,2,3,4,5,10,15,20,25,30,40,42,50,60,70,75,80,120,125,144,150,175,190,199,200] For each iteration of the loop, your answer must include the values of I and r at the start of the iteration, as well as the value of m, if any, computed in that iteration. b) Consider interpolation search on a sorted array A[0,,n1] that stores real numbers. Suppose that A[i]=ai+b for all i{0,,n1}, where a and b are real numbers and a!=0. For example, if A={5,7,9,11,13,15} then a=2 and b=5. Prove that the interpolation search on A takes O(1) (no matter if the search is successful or unsuccessful). c) Recall that the worst-case search time for interpolation search is (n). Give a family of an arrays An, each with n distinct values, (i.e., by defining An[i]=f(i) for some function f ) as well as search keys kn such that searching for kn in An has runtime (n). (There are many examples of such inputs, but you only need one for each n ). You must prove the runtime of the algorithm on your inputs is in (n)