Comment by YetAnotherNick

I think that is definition of approximate algorithm, not randomized algorithm. Quicksort is a classic randomized algorithm, but it is not approximate.