Use the master method to show that the solution to the binary-search recurrence \(T(n) = T(n/2) + \Theta(1)\) is \(T(n) = \Theta(\lg n)\). (See Exercise 2.3-5 for a description of binary search.)

\(a = 1\), \(b = 2\) and \(f(n) = 1\).

Case 1 does not apply since \(f(n) = O(n^{\log_{2}1 - \epsilon}) \implies \epsilon < -1\).

Case 2 applies since \(f(n) = \Theta(n^{\log_{2}1}) = \Theta(1)\), and thus the solution to the recurrence is \(T(n) = \Theta(n^{\log_{2}1} \lg n) = \Theta(\lg n)\).