Only need help with questions 3-6. Thank you!

Exercise 1 (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 - -1 if x does not exist in Sequence A. Algorithm description int divideSearch (A, p, r, x) if (r >= p) midpoint = p + (r-p)/2; if A[midpoint] == x return midpoint; if A[midpoint] > X return divide Search (A, p, midpoint-1, x); else return divide Search (A, midpoint+l, 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 1. a. Execute manually divide Search(A,1, A.length, 68). What is the output? b. Execute manually divideSearch(A,1, A.length, 20). What is the output? C. Execute manually divide Search(A,1, A.length, 92). What is the output? d. Execute manually divideSearch(A,1, 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 ((if A[midpoint] == x) and (if A[midpoint] > x)). Express the running time T(n) 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 Tin) using the master method