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
- 10142 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 meant by relay & co-ordination at substation engineering ?
how can i install windows-xp operating system in single time to 50 computersconnected in a LAN.
what is a pointer in c language?
searching a B-tree indexed tree compared to B+ tree is slow..True or false
as we know that java is a platform independent language, but we need jvm for the same operating system why?
WAP in Java to print the format A B A B C D E D E
WHAT HAPPEN WHEN ANY SPINDLE RUN OVER 10 MM HEIGHT ABOVE BOLSTAR IN RING SPINNING FRAME
Whats the difference between following two array declaration in JAVA? int a[]={1,2,3,4,5}; int []a-{1,2,3,4,5};
what are purchase order , sales order idoc names and idoc types
good morning! can u briefly explain the concept of syllolism and wat it mean?
Key difference between ip10 and ip20 of ceragon equipment?
I am 2012 pass out b tech student(cse). i have recently started software manual testing class. Is this field is benefitial for me in future?
what is the difference between core java and advance java
how to send request to the direct server rather than proxy server
Write a function to print all the combinations of a string both uppercase and lowercase without altering the position of each letter.
