Answer / narina thakur

The average number of inversions in an array of N distinct
elements is N(N-1)/4

Proof:
Total number of inversions in a list L and its reverse Lr
is N(N-1)/2. Average list has half this amount, N(N-1)/4.

Answer / vivek sampara

How can you have the reverse of the list when it says i<j
and A[i]>A[j] ?

The Array always starts with A[0] till A[n] .

We cant have it reversed as A[n] to A[0].

The And the sequence of the total number of pairs are

n(n+1)/2

because the pairs are (n,n-1),(n,n-2),(n,n-3).....(n,0)
and (n-1,n-2),(n-1,n-3),(n-1,n-4)......,(n-1,0)
and (n-2,n-3),(n-2,n-4),(n-2,n-5)......,(n-2,0)


the list is n+(n-1)+(n-2)+.....3+2+1+0

reversing we'll get

1+2+3+4.....(n-1)+n =n(n+1)/2

So the average number of inversions are

(n(n+1)/2 )/n

= n(n+1)/2n

which collection enforces type safety?

0 Answers  

---

how can i implement a program of polynomial adding,multiplication,through c language???

0 Answers  

---

Please derive the formula for the area of a circle.

0 Answers  

---

difference between a for loop and a while loop? what are its uses in c language?

0 Answers  

---

how to generate linked implementation of sparse matrix?

0 Answers  

---

SQL How can make delete and insert in one query

0 Answers  

---

What is the pressure in co2 cartridge in a DCP 5 kg extinguisher.

0 Answers   L&T, Samsung,

---

give me a example of an application of Low severity & high priority.

0 Answers   DataCore, DCPL,

---

difference between tcp ip and open system interconnection

0 Answers  

---

Whay we use gigabite ethernt

0 Answers   IBM,

---

Full form of Abt Meter

2 Answers   ABB,

---

PLEASE SEND ME NIC SCIENTIFIC OFFICER-2009 EXAM PATTERN AND QUESTION PAPERS

0 Answers   NIC,

---