Re:Vitter's reservoir sampling algorithm D: randomly selecti...
by robrenaud on Monday April 04, 2016 @07:58AM
(#11421151)
Not o (little oh), but rather O (big oh).
There is a difference between them. Little oh roughly means "grows strictly slower than, in the limit", where as big oh roughly means "grows no faster than, in the limit".
http://stackoverflow.com/questions/1364444/difference-betwee...
http://www.ittc.ku.edu/~jsv/Papers/Vit87.RandomSampling.pdf
In short, it's worth reading Vitter's paper, the original post is just a post containing the C code, but the discussion of the algorithm and the comparison with the alternatives is in the paper.
(Edit: corrected the notation of O() as robrenaud suggested)