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.