Use Theorem 14.1 to prove that binary search requires (log n) time. Theorem 14.1 (The Master Theorem) For any recurrance relation of the form T(n)

Use Theorem 14.1 to prove that binary search requires Θ(log n) time.

Theorem 14.1 (The Master Theorem) For any recurrance relation of the form T(n) = aT(n/b) + cnk, T(1) = c, the following relationships hold. T(n) = S (nlog, a) (nk logn) (nk) if a > fk if a = bk if a < fk.