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

Person who dicided to go to weekend trip should not exceed 8 hrs driving in a day. Average speed of forward journey is 40 miles/hour . Due to traffic in sundays ,in return journey average speed is 30mph . How far he can select a picnic spot ?

4 Answers TCS,

what are the various login options used in loadrunner tool to make a application performance testing

0 Answers

What do u mean constructor in java ?

1 Answers

what is recursion in c language?

0 Answers

hey,,,hi have taken an emergency date of 21st july...i was continuously checking for dates n i was not able to get a normal date n my school is starting from 8th of september...so plz tell me can i get a rejection based on this, that i have taken an emergency date?????

0 Answers

What is spooling and buffering?

0 Answers

in header files whether functions are declared or defined in c language?

2 Answers

If the length of a rectangle is increased by 30% and the width is decreased by 20%, then the area is increased by...

4 Answers College School Exams Tests, Infosys, Microsoft, TCS,

What is the procedure for taking leave while detecting Epf and Esi?

0 Answers

What is the pattern for HAL Online-exam?

0 Answers

difference between java programming and c programming??

1 Answers

CAN ANYBODY CAN SEND ME HEWITT PLACEMENT PAPERS(APTITUDE AND TECHNICAL).

31 Answers Ericsson, Hewitt, TCS,

For more Engineering AllOther Interview Questions Click Here