Time complexity?

Question

We are given a sequence of n nos. a1, a2, a3,.......an, we will assume that all the nos. are distinct. We say two indices i < j form an inversion if ai > aj .

How much time will it take to find total no. of inversions in the given array?

a) O(n²)    b) O(nlogn)    c) O(n)   d) none of these

Answer 1

Take array as: 4 1 5 3 2

Sorted: 1 2 3 4 5

Number of inversions:

for 1: 1 (how many numbers larger than 1 are on the left side of 1 in initial array)
for 2: 3
for 3: 2
for 4: 0
for 5: 0

So, total inversions = 1+3+2 = 6. 

An algorithm for finding this in $O(n \log n)$ is given in below link. 

https://www.cp.eng.chula.ac.th/~prabhas//teaching/algo/algo2008/count-inv.htm

Comments

Here it would be $nlogn$ only.

See the below link for more clarity:

https://www.quora.com/We-are-given-a-sequence-of-n-numbers-a1-a2-a3-a4-assuming-that-all-numbers-are-distinct-we-say-2-indices-I-j-from-an-inversion-if-ai-aj-Can-any-one-tell-me-algorithm-to-find-complexity-of-this-problem-in-nlogn-time

---

@akshshu

You can r@Arjun Sir's answer. It has been edited again.

---

@akshshu

You can recheck @Arjun Sir's answer. It has been edited again.