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
- 11351 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
Explain how to share outlook calenders and the type of permissions you need to assign?
what do you expect from this company?
Can you delink a payer from a bill to sold to ship to and then create a new payer on the existing bill to sold to ship to, this is where a pub or club changes licencees and we want to icolate the debt from the old owner but keep the sales history on the ship to/sold to
program for inter process communicatin using message sharing in unix c
there are 50 users in a network, one system is virus affected , how to find that virus affected system?
WHAT IS THE PROPER LOCATION OF SAMPLE POINT OF LPG SPHERE TANK?
Draw a pipeline configuration to carryout the following operations on the arrays of data represented by A, B, C, D, E and F. (A i represents the i th element of the array). (Ai × Bi + Ci × Di ) (Ei × Fi ) Show the content of the pipline for i = 1 to 5
Suppose that, even unrealistically, we are to search a list of 700 million items using Binary Search, Recursion (the algorithm given in class). What is the maximum number of comparisons that this algorithm must perform before finding a given item or concluding that it is not in the list?
Difference in NS and TIA type HRC fuses
PLEASE SEND ME NIC SCIENTIFIC OFFICER-2009 EXAM PATTERN AND QUESTION PAPERS
i made lan connections ,then how can i establish the network....with that connections only is the network is established ...tell me the procedure for giving the lan connection for some(10) pc's?
when there is a parametrized constructor, and an object is created with no arguments. will the default constructor be called?
plz send me interview questions & answers of Data Structure
please send aptitude test papers for reference with answers
sir, plz send me the question regarding DMS gr1 questions of previous year as my exam is on 27/09/08...thanking u in advance...
