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

Tell me all about production of drought and its losses In the boiler?

0 Answers   Dairy Science College,

---

I want old SBI question papers plzzzzzzzzz

0 Answers  

---

explain about scope and storage class in oops

0 Answers  

---

what is meant by safety in construction?

3 Answers   CAE,

---

i am satish i want to preapare for group-1 exams so please help me?

0 Answers  

---

---

In how many ways can you put numbers 1 to 9 without repeating in a 3*3 matrix,So that the total of elements in any row and column and diagonal is 15?

0 Answers   Amazon,

---

project plan for bug tracking system?

0 Answers  

---

int main() { int d = 10; int m = 2; int y = 3603; int c = 0; int val; val = ( d + m + y + (y/4) + c) % 7; cout << val; return 0; }

0 Answers  

---

How to get the code from internet while i am doing project

0 Answers  

---

is the RKDF university is aicte approved for b.tech in computer

0 Answers  

---

dam,rivers,states capt,

0 Answers  

---

Is there any difference between the concepts of encoding,decoding and encryption and decryption?

0 Answers  

---