Made Easy algorithms

Question

Given an array of n elements, two elements in the array a[i] and a[j] are said to be inverse only if a[i]>a[j] && i<j. What is the time complexity required to find the number of inverses in the given array using merge sort?

a) O(n)

b) O(n²)

c) O(nlogn)

d) O(logn)

Comments

Well Explained here: https://www.geeksforgeeks.org/counting-inversions/

Answer 1

Answer is Option B,

Largest possible inversions are possible when array is in decreasing order ,

Eg . [5,4,3,2,1]

therefore total pairs formed is nC2 ,

= n(n-1)/2

=O(n^2)

Therefore , TC = O(n^2)