Swipe to navigate through the chapters of this book
This chapter accomplishes two goals. First, it introduces a number of algorithms of a probabilistic nature. For this, it starts with a discussion of random number generators and related functions, followed by algorithms for shuffling a collection of objects, selecting a fair sample from a collection, and simulating a probabilistic event. Second, it uses elements of probability theory to compute the average complexity of some algorithms. It starts with simpler cases, such as the linear search, where the expected value of a variable is used. It follows with more complex cases, such as the bubble sort, where the expected value of a variable is combined with loop counting. This leads to the last section where conditional probabilities are used to prove the expected complexity of the Quicksort on the average.
Please log in to get access to this content
- Algorithms and Probabilities
- Springer International Publishing
- Sequence number
- Chapter number
- Chapter 6