Course contentsShow
← Computer Science
Lesson 137 of 2,8723. Probability for Computer ScienceFree lesson

Expected Value and Variance in Algorithm Analysis

Apply expectation and variance to analyze randomized algorithms, understanding average and typical performance.

Expected Value and Variance in Algorithm Analysis

What you'll learn: How to use expected value and variance to predict and understand the performance of randomized algorithms.

Why This Matters

When analyzing randomized algorithms—algorithms that make random choices during execution—we can't just ask "how long does it run?" Instead, we ask: "On average, how long does it run?" and "How much does the runtime vary?"

The Core Idea

Expected value tells you the average performance across all possible random outcomes. If a randomized search takes 3 steps half the time and 7 steps the other half, its expected runtime is (3 + 7)/2 = 5 steps.

Variance tells you how spread out the performance is. Low variance means the algorithm is predictable—most runs finish near the average. High variance means some runs might be much faster or slower than expected.

How It Works

When you have a randomized algorithm:

  1. Identify the random variable (e.g., number of comparisons, runtime)
  2. Calculate expected value using probability distributions: E[X] = sum of (outcome × probability)
  3. Calculate variance to understand consistency: Var(X) = E[X²] - (E[X])²

Example Insight

Suppose a randomized quicksort has:

  • Expected comparisons: E[X] = n log n
  • Variance: Var(X) = some small value

This tells you: "On average, expect n log n comparisons, and most runs will be close to this." Low variance means reliable performance; high variance means unpredictable runtimes.

Key Takeaway: Expected value reveals the average-case performance of randomized algorithms, while variance shows how consistent or unpredictable that performance is—both are essential for understanding real-world behavior.