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

what is need of interface. what is the diff b/w interface and abstract class

0 Answers

How to control the Relative humidity in Air handling unit in Pharmaceutical company ,the AHU is comprised with DX system(Cooling coil) and dry heaters. We are facing the RH issue low side and higher side.

0 Answers Archimedis Healthcare,

HI frds,,,am final yr IT student.. i secured 81% in x 55% in xii 87% in Btech upto last sem (no standing arrears..) i dt kw clearly abt MNC eligibility criteria.. i heard tat TCS hired 1y abv 60% 1y..so pls help me.. wic cmpnys r anouncd 55% may eligibl in 2011??? pls rly me clearly and sugst som of d compny names...

1 Answers

how to find number of possible trees in a given tree with n nodes?

1 Answers TCS,

What is smoke testing?

1 Answers

#include<stdio.h> int main() { char *ptr; char string[] = "How are you?"; ptr = string; ptr += 4; printf("%s",ptr); return 0; }

5 Answers Wipro, Zoho,

What are special features of Silk Test ? In what way it is advanced than QTP?

0 Answers

what is node class?

0 Answers Oracle,

How to Define the defect density?