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?
- 2 Answers
- 10550 Views
- Infosys, I also Faced
- E-Mail Answers
Answer Posted / 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 View All Answers
i need to know abt renault nissan company and the rounds and type of questions asked by today
how convert the spiral model to prototype model ?
find the salary of an employee where employee number is known
Is printf(?%d?,p); valid?
Differentiate y = sinx + cosx + tanx
what is c dot
Whet is KCFT and difference between CFM and KCFT
Please. Does someone know how to inicialize tapes in ATL? I need have 100 tapes to init inside the ATL, how is the process to complete this request?
sir/medam i had completed my B-TECH(CSE)2011 with 61%.i have to go USA for futhure studies.i dnt know what is steps for do futhure studies in USA so could you please tell me
Apply Newton?s method to compute the approximate value of root 2. Start the iteration from x0=1, and obtain two iterations.
i cannot go to my computer to set up why?
THESE POSTS ARE FOR THE DURATION OF FIVE YEARS. AFTER COMPLETION OF FIVE YEARS, THE PERSONNEL POSTED AGAINST THESE POSTS ARE LIKELY TO BE CONTINUED IN NIC. CAN Any body say that what it will be happened after 5 years? does they through us out from NIC? Is it a temporary job of 5 years is the probation period?
How do aeroplanes fly? Why can some fly up-side down?
can you provide me uniken pvt ltd. technical interview question and answer?
how configur net and vpn on cisco product
