Question

Under what case of Master’s theorem will the recurrence relation of merge sort fall?

(a) 1

(b) 2

(c) 3

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

I have been asked this question during an internship interview.

Enquiry is from Masters theorem topic in chapter Recursion of Data Structures & Algorithms II

Answer 1

The correct option is (b) 2

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