Question

What is the average case time complexity of merge sort?

(a) O(n log n)

(b) O(n^2)

(c) O(n^2 log n)

(d) O(n log n^2)

I had been asked this question during a job interview.

This key question is from Sorting in section Sorting of Data Structures & Algorithms II

Answer 1

Correct choice 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. It is found to be equal to O(n log n) using the master theorem.