About this document
Understanding Randomized Algorithms by tmmbt is a document available to read on EtoBox.
This document discusses randomized algorithms and how they are analyzed. It introduces two types of analysis bounds for randomized algorithms: expected bounds and high-probability bounds. Expected bounds provide the average cost across all random choices, but some runs may be more or less costly. High-probability bounds indicate that the cost is unlikely to exceed some bound, being true with probability 1 - 1/nk for some constant k > 1. Expected bounds are useful for analyzing work, while high-probability b
- Author
- tmmbt
- Language
- EN