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
- 11313 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
Hello sir i finished my BE computer 2009 batch. I'm not gud at programming like 0 knowledge and i'm not interested in it too . Except this programming field is anyother option to afford into a new one ??????? can anyone help me plz
BEL old probationary engineering questions and answers
what is the class of generator A b & c
Write a C/C++ program that connects to a MySQL server and checks if the InnoDB plug-in is installed on it. If so, your program should print the total number of disk writes by MySQL.
what two ways you can use to ensure that visual basic does not allow uncleared variables?
how to join two table those stored on different database.
hello sir,pls fdorward previous group-I exam papers .....
Difference in NS and TIA type HRC fuses
what is isolator
Hi, I am preparing for Assistant Motor Vehicle Inspector (AMVI) exam.If any body having old question papers please send.My mail id is siyadndd@gmail.com
hai iam selected in po exam in allahabad bank . my interview date is 02-06-2009. so plese send me some sample question on my email. my email is nitinbikhani@yahoo.com
draw the diagram of double earthing
int i=~0; uint j=(uint)i; j++; printf(“%d”,j); what is the use of "uint" int the above code
what are the areas of improvement required in yourself to achieve your career goals? Describe what you are doing/plan to do to address the areas of improvement
5. Can you work well under deadlines or pressure?
