Use the master method to show that the solution to the binary-search recurrence is . (See Exercise 2.3-5 for a description of binary search.)

In the given recurrence, and . Hence, and . Hence case 2 of master method applies.

Hence,

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.