Numerical Methods and Optimization

190 Numerical Methods and Optimization: An Introduction

Therefore, the average running time of Quicksort is O(n log n).

9.3 Randomized Algorithms

A randomized algorithm is an algorithm in which some decisions depend

on the outcome of a coin flip (which can be either 0 or 1). Two major types of

randomized algorithms are Las Vegas algorithms, which always yield a correct

answer, but take random running time; and Monte Carlo algorithms,which

run in predefined time and give a correct answer with “high probability.” For

a problem of size n,wesaythat

p =1−

1

n

α

=1− n

−α

,

where α>1, is a high probability.

We say that a randomized algorithm takes

˜

O(f(n)) of a resource ...