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
- 10156 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
HOW CAN YOU RELATE THE FUNCTION WITH STRUCTURE EXPLAIN WITH APPROPRIATE EXAMPLES
How to recyling of Expired Computer/Laptop,Mouse,CPU & Key Board (Warranty)?
what two ways you can use to ensure that visual basic does not allow uncleared variables?
differance between radix sort and radix exchange sort
what is the program to find out the smallest word in a sentence? like if the sentence is : this is my room. then out put will be : is
as a fresher what is the format for resume and suggest me some career objectives too........
i cannot go to my computer to set up why?
Explain what is meant by repetition of information and inability to represent information. Explain why each of these properties may indicate a bad relational database design.
nohup sort employees > list 2 > error out & what will happen?
plz tell me which books r important for gate exam (CSE)
If there's any possiblity for the Enginnerring graduates, Who had backlogs in there acedmic to get a Good MNC job?
i want to do oracle certification..could any one pleas tell me what is the level 1 certification exam in oracle? how do we get dumps?
I want to test the applications installed on the client machine using the QTP installed on the server machine.But the requirement is like that client machines do not have there own CPU's they are just dummy workstations on which the applications are excesible.So where all places QTP should be insalled in theis client server architecture.How many licenses required of what type.Please explain in details .Its urgent. Thanks
difference between a for loop and a while loop? what are its uses in c language?
Create an midp application which examines that a phone number which has enters is in the given format * Area code should be one of the following:040,041,050,0400,044
