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

Growth Rates and Dominant Terms

Identifying which terms matter most as input grows large and ignoring lower-order terms.

Growth Rates and Dominant Terms

What you'll learn: How to focus on the terms that matter most when analyzing how an algorithm's runtime grows with larger inputs.

When analyzing runtime, you often end up counting operations and get expressions like 5n² + 3n + 7. But as input size n grows large, not all parts of this expression matter equally.

The Dominant Term Concept

Think of terms like runners in a race where the finish line keeps moving farther away. The dominant term is the one that "runs fastest" – it grows so much larger than the others that the slower runners become irrelevant.

For 5n² + 3n + 7:

  • When n = 10: 5(100) + 3(10) + 7 = 537
  • When n = 1000: 5(1,000,000) + 3(1,000) + 7 = 5,003,007

Notice how 5n² contributes 5,000,000 while 3n adds only 3,000 and the constant 7 is negligible. The quadratic term dominates.

Common Growth Rates (Slowest to Fastest)

  • Constant: 1 — never changes
  • Logarithmic: log n — grows very slowly
  • Linear: n — doubles when input doubles
  • Quadratic: n² — quadruples when input doubles
  • Cubic: n³ — grows even faster
  • Exponential: 2ⁿ — explodes rapidly

Why We Ignore Lower-Order Terms

When n is large (which matters most for performance analysis), the dominant term completely overshadows everything else. We simplify 5n² + 3n + 7 to just n² because that's what truly dictates growth behavior.

Key Takeaway: When analyzing algorithm growth, identify the fastest-growing term – it determines how runtime scales with large inputs, making all other terms insignificant by comparison.