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

explain in detail about life cycle of thread

0 Answers

describe about storage allocation and scope of global,exterm,static,local and register variables in c language?

0 Answers

need tcs questn papers from 2007 to 2009 plzzzmail to 9015.rama@gmail.com its urgent

0 Answers

Explain the following program segment. f(){ int *b; *b=2; }

0 Answers Geometric Software,

how to avoid a class from getting inherited but respective class should be able to instantiate ?

0 Answers

DVC2000 performent: travel ??? and not output signal

0 Answers

What is Moore's law and what limits the size of a computer chip?

0 Answers

MY QUERY IS REGARDING AS/400. I AM FACING A PROBLEM IN UPDATING A PF COZ IT IS GETTING LOCKED SO I USED CHAIN(N) INSTEAD OF ONLY CHAIN.I ALSO TRIED UPDATE(E) ALONG WITH CHAIN(N),ITS NOT GIVING ANY ERROR BUT AT THE SAME TIME NOT UPDATING THE PF

0 Answers Accenture,

I am IT engineer how IT would be useful in banking?? what best answer would be given for this question???

0 Answers IBPS,

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.

1 Answers

Stable storage cannot be implemented. (A) Explain why it cannot be. (B) Explain how database system deal with database applications

3 Answers SCS,

is java supprot the complier time pollymorphism or run time pollymorphism ... why

0 Answers HCL,

For more Engineering AllOther Interview Questions Click Here