Exercise I (50 points) Divide Search Consider the algorithm divide Search(A, p, r, x): the description of this algorithm is provided below. Inputs: a sorted array A - index p of the first element - index r of last element an element x to search Output: index of element x in Sequence A if x exists in A - if x does not exist in Sequence A. Algorithm description int divide Search (A, PI, x) if (r = p) midpoint = P + (r-p)/2; if A[midpoint] == x return midpoint; if A[midpoint] > X return divideSearch (A, D, midpoint-1, x); else return divideSearch (A, midpoint+i, r, x); return -1; The objective of this exercise is to derive the time complexity (running) time of the divide search. (If interested, you could read about divide search on Wikipedia) 1) (6 points) Let A = (-4, 6, 10, 14, 19, 28, 35, 36, 40, 57, 64, 68, 72, 92). Assume that the index of the first element is I. a. Execute manually divide Search(A, I, A.length, 68). What is the output? b. Execute manually divide Search(A, I, A.length, 20). What is the output? C. Execute manually divide Search(A, I, A.length, 92). What is the output? d. Execute manually divideSearch(A, I, A.length,-4). What is the output? 2) (2 points) Which operation should you count to determine the running time T(n) of the divide search in a sequence A of length n? 3) (12 points) Let us count the comparisons (it A[midpoint] == x) and (if A[midpoint] > x)). Express the running time Tn) as a recurrence relation. 4) (12 points) Solve the recurrence relation T(n) using the recursion-tree method 5) (8 points) Solve the recurrence relation T(n) using the substitution method 6) (10 points) Solve the recurrence relation T(n) using the master method