Question

Under what case of Master’s theorem will the recurrence relation of binary search fall?

(a) 1

(b) 2

(c) 3

(d) It cannot be solved using master’s theorem

The question was asked in examination.

My doubt stems from Masters theorem in section Recursion of Data Structures & Algorithms II

Answer 1

Right answer is (b) 2

Best explanation: The recurrence relation of binary search is given by T(n) = T(n/2) + O(1). So we can observe that c = Logba so it will fall under case 2 of master’s theorem.