Question

What is the time complexity of merge sort in the worst case?

• A. $O(n \log n)$
• B. $O(n^2)$
• C. $O(n)$
• D. $O(\log n)$

Hint:

Merge sort’s consistent $O(n \log n)$ complexity makes it efficient for large datasets.

Answer 1

The Correct Option is A

Merge sort divides the array into two halves recursively until single elements remain, then merges them back in sorted order.
The recurrence relation is:
\[ T(n) = 2T(n/2) + O(n) \]
- Dividing: $O(1)$
- Merging: $O(n)$
- Depth of recursion: $\log n$
Total time: $O(n) \cdot \log n = O(n \log n)$.
This holds for all cases (best, average, worst).