Randomized Algorithms

Randomization has broader ramifications than being cleverly used to speed up Quicksort. Randomized Quicksort is one example of an entire class of algorithms known as randomization algorithms (or randomized algorithms).

The term randomization algorithm is a fancy name for an algorithm that uses randomization somewhere as part of its instructions. Randomized Quicksort is such an algorithm since its first step is to use randomization to shuffle the array. Randomized algorithms serve as a major theme throughout this book since they have so many applications.

As you’ll discover throughout our journey, randomization can be used to perform all sorts of optimizations. With Randomized Quicksort, you saw how randomization improved the speed for worst-case scenarios. Some other randomization algorithms, though, use randomization to increase speed in all scenarios. There are algorithms that use randomization to save memory, while others use randomization to increase accuracy. (You’ll see what that means in Chapter 9, .) And sometimes, randomization is at the core of the algorithm itself, and without randomization, the algorithm wouldn’t work at all.

Before we explore other types of randomization algorithms, we should first answer some fundamental questions about randomization in general. For example, how does a computer shuffle an array? And what is the time complexity of shuffling an array?

For that matter, let’s start with an even more basic question: how does a computer choose a random number?