What is the complexity of Merge Sort?
| What is the complexity of Merge Sort?
A. O(n<sup>2</sup> log n)
B. O(n log n)
C. O(n<sup>2</sup>)
D. O(n)
Please scroll down to see the correct answer and solution guide.
Right Answer is: B
SOLUTION
Merge sort:
Merge sort is based on the divide and conquer approach.
Recurrence relation for merge sort will become:
T(n) = 2T (n/2) + Θ (n)
Using Master’s theorem
T (n) = n × log2n
Therefore, the time complexity of Merge Sort is θ(nlogn).