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
10402 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

Write a function that responds to a click anywhere on the page by displaying an alert dialog. Display the event name if the user held Shift during the mouse click. Display the element name that triggered the event if the user held Ctrl during the mouse click.

0 Answers HCL,

Implement the dictionary operations INSERT, DELETE, and SEARCH using singly linked, circular lists. What are the running times of your procedures?

0 Answers

Based on the Job Description above, please indicate in details why you are a good match for this position?

0 Answers

write a program to accept 25 characters and at the end display the largest and smallest among them.

0 Answers

can i clearly know courses under oracle

0 Answers

How to work Air cooled and water cooled chiller?

0 Answers

Tell me all about production of drought and its losses In the boiler?

0 Answers Dairy Science College,

how to join two table those stored on different database.

0 Answers

What is OHNS Material and can anybody explain the Chemical & Physical Properties of Same. Which Technical Standard Book shows this Specification. Why can't we use En series instead of OHNS. Where it is specifically Used.

3 Answers Advanced Bolting Solutions,

what is the difference between physical address and logical address?

0 Answers

Can a Student without engineering background appear for GRE means If he did Bachelor of science in Information technology i.e BSc(IT).

0 Answers

For more Engineering AllOther Interview Questions Click Here