The average-case and worst-case complexities of the Merge Sort algorithm are:
20072007
The average-case and worst-case complexities of the Merge Sort algorithm are:
- A.
O ( n2 ), O ( n2 )
- B.
O ( n2 ), O ( n log2n )
- C.
O ( n log2n ), O ( n2)
- D.
O ( n log2n ), O ( n log2n )
Attempted by 379 students.
Show answer & explanation
Correct answer: D
Merge Sort is a divide-and-conquer algorithm that recursively splits the array into halves and merges them back together. The merging step takes O(n) time, and there are log n levels of recursion. Therefore, the total complexity is O(n log n). This performance remains consistent regardless of input order, so both average and worst-case complexities are O(n log n).