Please show all steps.

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, p, r, x) if (r >= p) midpoint = p + (r-p)/2; if A[midpoint] == x return midpoint; if A[midpoint] > x return divideSearch/A, P, midpoint-1, x); else return divide Search (A, midpoint+1, r, x); return -1; The objective of this exercise is to derive the time complexity (running) time of the divide search. (lf interested, you could read about divide search on Wikipedia) 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 Tn) using the master method