Question

What is the average case time complexity of standard merge sort?

(a) O(n log n)

(b) O(n^2)

(c) O(n^2 log n)

(d) O(n log n^2)

This question was addressed to me during an interview for a job.

My question comes from Sorting topic in division Sorting of Data Structures & Algorithms II

Answer 1

Right answer is (a) O(n log n)

The best I can explain: The recurrence relation for merge sort is given by T(n) = 2T(n/2) + n. This can be solved using master’s theorem and is found equal to O(n log n).