Selection in Expected Linear Time

Use Randomized-Partition ( A, p, r ) from randomized quick sort. Consider only the sub array were a_i¢ is:

Randomized-Select (A, p, r, i)

1. if p = r
2.    then return A[p]
3. q ¬ Randomized-Partition (A, p, r)
4. k ¬ q - p + 1 ( length of first sub-array
5. if i £ k
6.    then return Randomized-Select (A, p, q, i)
7. // in first sub-array
8.    else return Randomized-Select (A, q + 1, r, i - k)
9. // in second sub-array, (i - k)^th order

As with randomized Quick-Sort, worst-case running time is Q  (n²)

What is the expected running time?

i

Recall i = 1 with probability 2/n.

i = 2,3,4,...n - 1 with probability 1/n

T ( n ) £

1/n ( T ( max ( 1, n-1 ) ) +

n -1 å k = 1   T ( max ( k, n - k ))) +

O (n)

Maximum because the upper bound occurs when the partitioning is against us.

£ 1/n ( T ( n-1 ) +  2

n -1 å k =é n/2 ù  T ( max ( k, n - k )))   +  O (n)

= 2/n

n -1   å T ( k )   +  O ( n ) k =é n/2 ù

.

Assume T ( n )  £   c n and substitute

T ( n )   £

2/n

n-1 å k =é n/2 ù  c k  +  O (n)

= 2 c / n (

n-1 å   k  - k = 1

é n/2 ù -1 å  k      ) k = 1

+ O ( n )

= 2 c / n ( (n-1) n / 2 - (( é n 2 ù -1 ) é n 2 ù / 2 ) + O ( n )

£ c ( n-1 ) - c/n ( n/2 - 1 ) ( n/2 ) + O ( n )

= c ( 3/4 n - 1/2 ) + O ( n )

£  c n ,

c s.t. c ( n/4 + 1-2 ) >> O ( n )

T ( n ) = O ( n ) for randomized select.