Linear-Time Selection

1. Problem Definition:

    Input: array A with n distinct numbers and each number i is in {1, 2, 3, ... , n}

    Output: ith smallest element in A

 

2. Randomized Selection:

    RSelect(array A , length n, order statistic i )

    a)  if n = 1 return A[1]

    b)  choose pivot p from A uniformly at random

    c)  partition A around p , let j = new index of p

    d)  if j = i , return p

    e)  if j > i , return R ( 1st part of A, j -1 , i )

    f)  if j < i , return R( 2nd part of A, n - j , i - j )

 

3. Running Time of RSelect depends on which pivots get chosen. ( could be as bad as O(n^2) )

    Best pivot is the median ( but choosing the media needs RSelect...)

    For the best case : T(n) <= T(n/2) + O (n) , per Master Method, T(n) = O(n)

 

4.  RSelect Theorem : for every input array of length n , the average running time of RSelect is O(n).

    -- it holds for every input (no assumption on data)

    -- "average" is over random pivot choices made by the algorithm

 

5. Tracking progress via phases :

    RSelect is in Phase j if current array size between (3/4) ^(j+1) n and (3/4)^j n

    Let random variable Xj = the number of recursive calls during phase j

    So running time of RSelect <= Sum(phase j ) {Xj * c * (3/4)^j * n }

 

6.  If RSelect choose a pivot giving a 25-75 split (or better)  then current phase ends.

     The probability of 25-75 split or better is 50%

      E[Xj] <= expected number of times you need to flip a fair coin to get one "head"(head <==> good pivot)

      Let N = number of coin flips until you get head.

      E[ N] = 1/2     *      1              +    1/2 ( 1               +             E[N] )

                 probability of head           probability of tail             # of further coin flips

      E[N] = 2 , so E[Xj] <= E[N] = 2

 

7.  Running time of RSelect <= Sum(phase j) {Xj * c * (3/4)^j * n }

                                            <= 2* c*n*Sum(phase j)  { (3/4)^j}

                                            <= 2* c*n* 1/(1-3/4) = 8cn = O(n)

 

8.  Deterministic Linear-Time Selection:

    Goal: find pivot guaranteed to be pretty good.

    key idea: use "median of medians"

 

9.  Deterministic ChoosePivot(A,n) :

     a) logically break A into n/5 groups of size 5 each

     b) sort each group (e.g. using inertion sort)

     c) copy n/5 medians into new array C

     d) recursively compute median of C

     e) return the median of C as pivot.

 

10.  DSelect(array A, length n, order statistic i)
    a) Break A into groups of size 5, sort each group
    b) C = the n/5 “middle elements”
    c) p = DSelect(C,n/5,n/10) [recursively computes median of C]
    d) Partition A around p , j = new index of p
    e) If j = i return p
    f) If j > i return DSelect(1st part of A, j-1, i)
    g) [else if j < i] return DSelect(2nd part of A, n-j, i-j)

 

11.  DSelect Theorem:

        For every input array of length n, DSelect runs in O(n) time

        It's not as good as RSelect in practice due to :

        a)  worse constant factors

        b) not in place

 

12.  Soring an array of 5 elements takes constant time, So the 1st step of DSelect takes O(n)

 

13.  Let k = n/5 = # of groups

       Let x(i) = ith smallest of the k "middle elements".

       So the pivot = x(k/2).

       So there are at least n/2 * 3/5 elements smaller than pivot and at least n/2 * 3/5 elements bigger than pivot.

       So the second recursive call of DSelect guaranteed to be on an array of size <= 7/10 n

      

 14.  Let T(n) = maximum running time of DSelect on an input array of length n.

        There is a constant c >= 1 such that :

        a) T(1) = 1

        b) T(n) <= cn + T(n/5)  + T(7/10 n)

        Inductive proof for T(n) = O(n) :

        Suppose T(n) <= an , a is a constant (for all size < n)

        T(n)  <= cn + a (n/5) + a (7/10 n) = (c + 9/10 a) n

         To let (c + 9/10 a) n <= an , 10c <= a, let a = 10c , then for all n, T(n) <= an