big o - How do you calculate the big oh of the binary search algorithm?

Question

I'm looking for the mathematical proof, not just the answer.

Answer 1

The recurrence relation of binary search is (in the worst case)

T(n) = T(n/2) + O(1)

Using Master's theorem

• n is the size of the problem.
• a is the number of subproblems in the recursion.
• n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)
• f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems.

Here a = 1, b = 2 and f(n) = O(1) [Constant]

We have f(n) = O(1) = O(n^log_ba)

=> T(n) = O(n^log_ba log₂ n)) = O(log₂ n)