An inversion is an array of numbers is any pair (i,j) such
that i<j and A[i]>A[j]. What is the average number of
inversions in an array of n ?
distinct numbers?
- 2 Answers
- 10164 Views
- Infosys, I also Faced
- E-Mail Answers
Answer Posted / 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
| Is This Answer Correct ? | 8 Yes | 8 No |
Post New Answer View All Answers
What is frog testing? What is cone model?
What is the main difference between binary and counting semaphore?
what is mean by tranducer
please answer the following question: A table contains the monthly sales data for the 12 months of a year and for the 4 sales zones where each zone has 8 districts.The table is defined in WORKING-STORAGE SECTION.What is the size of the defined table in number of bytes? write statements to calculate the total sales for each month.
what should i say in the interview if interviewer asks me "why did you choose IT instead of your core group?"
Explain about a light bulb
Please mail me the sample papers of PNB for the post Dy. Manager.
sample sbi questions paper
How can we share data between actions in qtp..pls tell me
i possess a little knowledge of core java . so is it will be difficult for me to start advanced java?
what is overflow and what are the conditions for which overflow possible?
Is printf(?%d?,p); valid?
Explain Belady's Anomaly.
What is spooling and buffering?
what is typa casting and type conversion ?
