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

Comparing Growth Rates

Ranking common Big-O classes from fastest to slowest and understanding practical implications for scalability.

Comparing Growth Rates

You'll learn how to rank algorithm complexities from fastest to slowest and why this matters for real-world scalability.

Now that you've met individual Big-O classes, it's time to line them up and see how they compare. Not all algorithms age equally as data grows—some stay blazingly fast while others grind to a halt.

The Speed Hierarchy (Fastest → Slowest)

From best to worst, here's how common Big-O classes rank:

  1. O(1) — Constant: Always the same speed, no matter the input size
  2. O(log n) — Logarithmic: Grows very slowly (doubles input, adds one step)
  3. O(n) — Linear: Doubles input, doubles time
  4. O(n log n) — Linearithmic: Slightly worse than linear
  5. O(n²) — Quadratic: Doubles input, quadruples time
  6. O(n³) — Cubic: Doubles input, time increases 8×
  7. O(2ⁿ) — Exponential: Each additional input doubles the work
  8. O(n!) — Factorial: Catastrophically slow, explodes instantly

Why This Matters

Imagine processing user data. With 100 users:

  • O(n) takes 100 operations
  • O(n²) takes 10,000 operations
  • O(2ⁿ) takes more operations than atoms in the universe

At small sizes, the differences seem minor. But scale to 10,000 users, and O(n²) requires 100 million operations while O(n) needs just 10,000. The O(2ⁿ) algorithm? Forget it—it won't finish in your lifetime.

Rule of thumb: Anything worse than O(n²) is usually impractical for large datasets. Exponential and factorial algorithms only work for tiny inputs (typically n < 20).

Key Takeaway: Big-O classes form a hierarchy where small improvements (like O(n²) → O(n log n)) can mean the difference between an app that scales and one that crashes under load.