## Another note...

Posted Jan 19, 2012 9:23 UTC (Thu) by

**khim** (subscriber, #9252)

In reply to:

Is ignorance bliss? by cmccabe

Parent article:

Denial of service via hash collisions

There are another interesting fact related to Median of Medians algorithm: k must be at least 5 **only** because algorithm looks for **k**th largest element. In **this** case “k == 3” just does not work (as I've noted above). However if want to find **median** then not only "k == 3" works, it usually works better then “k == 5”. This is true because in the "find median" task you can throw away not just “top left” **xor** “bottom right” elements (as pictured in Wikipedia's illustration) but you can throw away **both** “top left” **and** “bottom right” elements. This will lead to complexity of T(N) ≤ C₁*N*(1 + (⅗) + (⅗)² + …) = O(N) for “k == 5” and to complexity of T(N) ≤ C₂*N*(1 + (⅔) + (⅔)² + …) = O(N) for “k == 3”, but ⅗ (for “k == 5”) comes from “⅕ + ⅖” (for two recursive calls) while ⅔ (for “k == 3”) comes from “⅓ + ⅓” (for two recursive calls). Thus in most cases version with “k == 3” is faster (because recursion depth is smaller), but difference is small and you must correctly handle case of N=3M+1...

(

Log in to post comments)