Course contentsShow
← Computer Science
Lesson 272 of 2,8727. Introduction to Complexity AnalysisFree lesson

Best-Case, Worst-Case, and Average-Case

Distinguishing between different input scenarios and why worst-case analysis is typically most important.

Best-Case, Worst-Case, and Average-Case

What you'll learn: You'll understand why the same algorithm can take different amounts of time depending on the input, and why we usually care most about the worst case.

When we count primitive operations to analyze runtime, we quickly realize the count can vary dramatically based on the specific input we give our algorithm—even if the input size stays the same!

Understanding the Three Cases

Imagine searching for a person in a classroom using Linear Search:

Best-Case: The person you're looking for is sitting in the very first seat. You check once and you're done! Operations: minimal.

Worst-Case: The person is in the last seat, or not in the room at all. You have to check every single seat. Operations: maximum.

Average-Case: On average, you'll find the person somewhere in the middle of the room, after checking about half the seats.

Why Worst-Case Matters Most

While it's nice when things go well (best-case), we design systems to guarantee they won't fail catastrophically. When building something reliable—like a search engine, banking system, or medical device—we need to know: "What's the longest this could possibly take?"

The worst-case gives us that upper bound. It's our safety guarantee. We can promise users: "This will never take longer than X time."

Average-case is useful too, but it requires knowing how inputs are distributed in real life—which is often hard to predict. Best-case is usually too optimistic to be useful for planning.

Example Counts

For Linear Search in an array of 10 elements:

  • Best-case: 1 comparison (found immediately)
  • Worst-case: 10 comparisons (found at end or not found)
  • Average-case: ~5 comparisons (found somewhere in middle)

Key Takeaway: The same algorithm performs differently on different inputs of the same size; worst-case analysis gives us the reliability guarantee we need, which is why it's the standard focus in complexity analysis.