[Solved] What is the time complexity of the code that uses merge sort for determining the number of inversions in an array?

What is the time complexity of the code that uses merge sort for determining the number of inversions in an array?

a) O(n2)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: d
Explanation: The code of merge sort is slightly modified in order to calculate the number of inversions in an array. So the time complexity of merge sort remains unaffected and hence the time complexity is O(n log n).

Comments