The Core Idea

Instead of asking:

“What is the worst-case running time for a specific input?”

We ask:

“What is the expected behavior when randomness is involved?”

Randomness can come from:

• assuming inputs are random (probabilistic analysis), or
• making the algorithm itself random (randomized algorithms).

The goal is reliability, not perfection.

Why This Way of Thinking Matters

Worst-case analysis can be misleading:

• it may almost never happen in practice
• it may depend on very specific inputs

Randomness helps us:

• avoid pathological (bad) cases
• get stable average performance
• reason about algorithms more realistically

This chapter teaches a mental shift, not just techniques.