need it ASAP..with detailed steps..

4. Assume you have a sorted array A of length n (where n is a power of 3) in front of you and you need to check if the value v is in it. You can check two values at positions n/3 and 2n/3 of the sequence A against v and eliminate ards of the sequence that cannot contain v, from further consideration. You then continue to search for v in the third you did not eliminate, in the analogous fashion. Write out recursive expression for the runtime T(n) of the algorithm that either ends by finding u in an array A of length n or reports that v is not in A. After you have the relation use Master Theorem to determine the runtime of the algorithm up to the asymptotic notation. (15 points)