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

write a c++ program to interchange two-integer number without using the third variable. use concept of constructor overloading.

0 Answers

Tell me about your parents?? Pls share any one best words...

0 Answers HGS, Hinduja,

I have Cleared Bank of India Clerical Examination.I just want to know how to prepare for interview and what are the parriculars that I have to submit......Pls someone help me with it

0 Answers

What is the use of taskbar?

2 Answers Quick Heal, TCS,

what is the need of constractor explain with sutable progarmming example

0 Answers

sir i m reject two time in u.s in spring intake now im taking a date of 1july-2010 in fall intake &im competed my bachlor degree(chem) in jun-2009 so what answer i give to visa officer ask me a what r u doing last 1-year bcoz i have no work expirience

0 Answers

IS THE SAMPLE POINT OF LPG SPHERE TANK PEFOR OR AFTER BUMP?

0 Answers

4. What is your typical way of dealing with conflict?

0 Answers Strad Energy,

what is a Additional domain ? what is a child domain?

0 Answers Tesco,

Hello everybody, I have applied for the AAI jr executive ATC exam. I am from CSE branch. Is Exam paper for the CSE and other branches same or not? Because I don't have knowlwdge on Electronic subject? Can any one please send me the previous exam papers for AAI Jr Executive of CSE branch My id is: naveen.kocherla@gmail.com Thanks and Regards Naveen

0 Answers

Q1. What do you mean by VPN(virtual private network)? Q2. What do you mean by switching and what are it's type? @3. What do you mean by ATM switching?

3 Answers

why do we join in bpo?

1 Answers

For more Engineering AllOther Interview Questions Click Here