Das Auswahlproblem
==================
Wolfgang Mulzer

SELECT(S, k)
  if |S| < 100 then
    use brute force
  q <- SPLITTER(S)
  S1 <- {s in S | s < q}
  S2 <- {s in S | s > q}
  if |S1| >= k then
    return SELECT(S1, k)
  else if |S1| = k-1 then
    return q
  else 
    return SELECT(S2, k - 1 - |S1|)


Wenn wir die Kosten für SPLITTER außer Acht lassen,
führt die Laufzeitanalyse zu der Rekursionsgleichung

     T(n) <= O(1) für n < 100
und  T(n) <= O(n) + T(3n/4),

welche sich zu T(n) = O(n) löst.