Chapter 9
Counting on Monte Carlo Algorithms

In the previous two chapters, we went on an exciting side quest and looked at the fundamentals of external-memory algorithms. But now it’s time to return to the topic of randomization.

Throughout this book, I’ve mentioned that there’s generally no one algorithm that is the “best algorithm.” That is, when choosing between two competing algorithms, there’s usually some sort of trade-off. Algorithm A may be faster, but Algorithm B may consume less memory. Algorithm C may be faster in the average case, but Algorithm D is faster in a worst-case scenario. Algorithm E may be better in terms of time and space, but Algorithm F may be simpler to implement and therefore have a smaller risk of bugs.

In this chapter, we’ll take a look at a new kind of trade-off: reducing accuracy for the sake of increasing speed. Now, this may not seem to make much sense at first, but trust me; it can be the key to solving some tough problems! Let’s take a look.