Interested to Buy Any Domain ? << Click Here >> for more details...
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
- 11458 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 JAR file,JNI,JFC??
operation of carrier aided protection and what is the basis for choice of frequncy in powerline carrier system
how to generate linked implementation of sparse matrix?
WHY WE SELECT U AS A PERTOLEUM ENGINEER THOUGH UR MARKS ARE LESS THEN OTHER APPLICANTS
Find the maximum stress intensity in the section?
WAP in Java to print the format AMIT M I T
Calculate the interstage pressure ratio per stage for a two stage compressor if the overall pressure ratio is 10.
what is the difference between error,exception,bug,defect,fault..?
i want to know details about SBI bank exam and date when to apply and what is the eligibility and the model papers related to it and various post available for Engineering in Information Technology.
explain various problem solving statagis
If memory is allocated to a class,when object of the class is created then how do we use the abstract class methods.coz v cant create obj of abstract class, only reference is created,when the abstract class data and members got the space in memory??
The old welding machine use electro- -magnetic winding to step up the current for welding rods,what is new principle inside the welding
Please if anybody have Vizag Steel Entrance exam papers or atleast Pattern of exam.Then please forward to my email- id: :srikanth.avanthi@gmail.com
find the salary of an employee where employee number is known
why every computer should have a boot strap routine?
