Median of medians is an approximate median selection algorithm used to supply a good pivot for an exact selection algorithm, such as quickselect. It finds an approximate median in linear time and can be used in quicksort to optimize the worst-case complexity to O(nlog n). It was published in Blum et al. (1973) and is sometimes referred to as BFPRT.

UC Berkeley

Spring 2020

This is an introductory course to computer science theory, exploring the design and analysis of various algorithms, number theory, and complexity. The prerequisites include familiarity with mathematical induction, big-O notation, basic data structures, and programming in a standard language.

No concepts data

+ 36 more concepts