Analysis of sorting Algorithm with probably wrong comparator? -

it interesting question interview, failed it.

an array has n different elements [a1 .. a2 .... an]（random order）.

we have comparator c, but has probability p return correct results.

now use c implement sorting algorithm (any kind, bubble, quick etc..)

after sorting have [ai1, ai2, ..., ain] (it wrong)。

now given number m (m < n), question follows:

1. what expectation of size s of intersection between {a1, a2, ...， am} , {ai1, ai2, ..., aim}, in other words, what e[s]?

2. any relationship among m, n , p ?

3. if use different sorting algorithm, how e[s] change ?

my idea follows:

1. when m=n, e[s] = n, surely
2. when m=n-1, e[s] = n-1+p(an in ain)

i dont know how complete answer thought solved through induction.. any simulation methods fine think.

hm, if a1,a2,...,an in random order (as stated in question), sorting , probability of correctness of comparator c not matter. question reduced expectation of length of intersection of 2 random subsets, each of size m, of {a1,...,an}.

the probability s k (m k)*((n-m) (n-k))/(n m), (a b) shall denote "a on b", number of possibilities chosing b elements a elements. (because second subset have choose k elements out of first subset , m-k elements rest.)

e[s] sum(0 <= k <= m) k*(m k)*((n-m) (n-k))/(n m), reduces m/(n m) * sum(0 <= k <= m) ((m-1) (k-1))*((n-m) (n-k)). sum basic (well-known) binomial identity giving ((n-1) (m-1)), m/(n m) * ((n-1) (m-1)) = m^2/n.