Randomization function: Difference between revisions

Revision as of 14:03, 12 November 2014

Revision as of 01:30, 19 July 2019

Line 8:

Randomizing functions are used to turn algorithms that have good [[expected value|expected]] performance for ''random'' inputs, into algorithms that have the same performance for ''any'' input.

For example, consider a [[sorting algorithm]] like [[quicksort]], which has small expected running time when the input items are presented in random order, but is very slow when they are presented in certain unfavorable orders. A randomizing function from the integers 1 to ''n'' to the integers 1 to ''n'' can be used to rerrangerearrange the ''n'' input items in "random" order, before calling that algorithm. This modified (randomized) algorithm will have small expected running time, whatever the input order.

==Requirements==

===Randomness===