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

What is the difference between operator overloading and function overloading in C when compared with C++?

0 Answers  

---

Write a regular expression for "Capgemini Services Pvt.Ltd"

0 Answers   Cap Gemini,

---

hi, please send me "state bank of india", last 5 years question paper with answers to my mail id.

0 Answers  

---

anyone send me aptitude and technical placement paper of Hewitt

0 Answers   Hewitt,

---

what is the formula/ ratio for hollow block? considering to a 40 kgs of portland cement.

0 Answers  

---

---

charak was the famous court physician of?

1 Answers   HCL,

---

hi i am kavita banjare iam 2007 passout studentin informaion technology. please give me technical paper.thanks sir............

1 Answers   Bajaj, Reliance,

---

through which part of the woman, wil the food go to foetus?

1 Answers   IOCL,

---

Email bombing is

1 Answers   NIC,

---

if a customer's blackberry stopped syncing their calendar wirelessly what would you do?if a customber deleted mail from his blackberry but it did delete from his mailbox how would ypu resolve this

0 Answers  

---

Hi i'm richa piplani applied for ATC(IT) if u have the syllabus & old question papers forward me.I will be very much thankful to you. piplani.richa@gmail.com and sonu_pips@yahoo.co.in

0 Answers  

---

1 2 3 2 5 6 7 8 3 find the next term in the series

3 Answers   Virtusa,

---