An inversion is an array of numbers is any pair (i,j) such that i<j and A[i

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?

Question Posted / guest

2 Answers
11169 Views
Infosys, I also Faced
E-Mail Answers

Answers were Sorted based on User's Feedback

An inversion is an array of numbers is any pair (i,j) such that i<j and A[i]>A[j]. What is ..

Answer / narina thakur

The average number of inversions in an array of N distinct
elements is N(N-1)/4

Proof:
Total number of inversions in a list L and its reverse Lr
is N(N-1)/2. Average list has half this amount, N(N-1)/4.

Is This Answer Correct ?

15 Yes

6 No

An inversion is an array of numbers is any pair (i,j) such that i<j and A[i]>A[j]. What is ..

Answer / 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

More Engineering AllOther Interview Questions

Describe an impedance matching circuit?

2 Answers

I have written some code of my project in java technology & some code in .net technology. Is it possible to integrate these into single project(module) to run complete project..?? if possible then how??

1 Answers

what should be the finish work of a carpenter per day

0 Answers

How will a tester be sure that He’s covered the entire functionality in his Test case and not missed out anything?

0 Answers

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?

0 Answers

What is RIA course certification.? which is the best institute for ria courses in bangalore ?

1 Answers Infosys,

what is memory interface????

1 Answers TCS,

how to find out the name of the users who are currently working starting with the same characters in unix os

0 Answers

difference between multi relational OLAP & multidimensional OLAP

1 Answers

computer is male or female.....???

0 Answers

Process-centered Methodologies , data-centered methodologies , object-oriented methodologies between differences

1 Answers

who is your role modal give in few sentances

0 Answers Bank Of America,

For more Engineering AllOther Interview Questions Click Here