Handbook of Randomized Computing: Volume I/II - Combinatorial Optimization Softcover reprint of the original 1st ed. 2001 edition

A brief introduction to randomized algorithms In the analysis of algorithms, at least three different measures of performance can be used: the best case, the worst case, and the average case. 2 For instance, the worst case run time of Hoare's quicksort is O(n ), whereas its average case run time is only O(nlogn).