Probability

Probability theory is a crucial tool in computer science, especially for the design and analysis of randomized algorithms and for understanding the average-case behavior of deterministic algorithms. A randomized algorithm uses a degree of randomness as part of its logic. For example, Quicksort's performance depends heavily on the choice of pivot; choosing a random pivot makes the worst-case O(n^2) scenario extremely unlikely, leading to an expected time complexity of O(n log n). Understanding basic probability concepts like sample space, events, conditional probability, and expected value is essential. The expected value of a random variable is the long-run average value of repetitions of the experiment it represents. In algorithm analysis, we are often interested in the 'expected runtime', which is the average runtime over all possible random choices the algorithm might make. Another key concept is linearity of expectation, which states that the expected value of a sum of random variables is the sum of their expected values, regardless of whether they are independent. This property is incredibly powerful and simplifies the analysis of many complex randomized algorithms. Problems in competitive programming often involve calculating the probability of a certain outcome or finding the expected value of some quantity, making a solid foundation in probability indispensable.