What is the complexity of Merge Sort?
2020
What is the complexity of Merge Sort?
Answer: C. O(n log n) — 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…
- A.
O(n)
- B.
O(n² log n)
- C.
O(n log n)
- D.
O(n²)
Attempted by 1220 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.
Explore the full course: Iocl Engineers Officers Grade A Paper 2
Loading lesson…