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 PID controller?

0 Answers   Cadila,

---

write a pgm to accept an array of names & name & check whether the name is present in the array. return the count of occurance. use following array as input; {"Dave","Ann","dev","merry"}

0 Answers  

---

What is meant by Insertion loss?

1 Answers  

---

what is the work of Loopback ?

0 Answers  

---

I have cleared SBT clerk exam and having interview on 29.I have completed my B.tech in IT.I would like to know the types of questions asked in the interview.

0 Answers  

---

explain software engineering practices

0 Answers  

---

10. Each alphabet stands for one digit in the following multiplication. T H I S x I S --------- X F X X X X U X ------------ X X N X X ------------ What is the maximum value T can take?

4 Answers   eLitmus, Infosys, Verchaska,

---

What type of questions are asked in interview?

0 Answers  

---

why need of new operator in java why not in c++

0 Answers  

---

What are saw filters used for?

1 Answers  

---

I need ECIL last year Question papers for COMPUTER SCIENCE ENGG. Please

0 Answers   Ecil,

---

hello sir,pls fdorward previous group-I exam papers .....

0 Answers   APPSC,

---