Posts tagged “complexity”
2 posts Subscribe by RSS
2 posts
Boyer–Moore majority vote: one candidate, one counter, and why you need a second pass
MJRTY (Boyer and Moore, 1980) picks a majority candidate with one value and one counter. Its rules, why it works, the wrong answer when no majority exists, and the second pass.
Median of Medians (BFPRT): Finding the k-th Smallest in Worst-Case Linear Time
How the PICK algorithm from the 1973 paper by Blum, Floyd, Pratt, Rivest, and Tarjan selects the k-th smallest value in worst-case linear time, and where the group size of five comes from.
No posts match. Try another word.