What is the complexity of Merge Sort?
2020
What is the complexity of Merge Sort?
- A.
O(n)
- B.
O(n² log n)
- C.
O(n log n)
- D.
O(n²)
Attempted by 491 students.
Show answer & explanation
Correct answer: C
Merge Sort follows the Divide and Conquer paradigm. The recurrence relation is T(n) = 2T(n/2) + θ(n). Solving this using Master's Theorem or a recursion tree gives a consistent time complexity of O(n.log n) for best, average, and worst cases. The correct option is C.