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.)
In the given recurrence, \(a = 1\) and \(b = 2\).
\(n^{\log_b a} = n^0 = 1\) and \(f(n) = \Theta(1) = \Theta(n^{\log_b a})\).
Hence case 2 of master method is applicable here.
\[T(n) = \Theta(n^{\log_b a} \lg n) = \Theta(\lg n)\]