Big-O Notation and Algorithmic Complexity
What you'll learn: How to describe and compare the scalability characteristics of algorithms using Big-O notation.
Understanding Algorithmic Complexity
When evaluating performance, we need a standard way to describe how an algorithm's resource consumption grows as input size increases. Big-O notation provides this language, expressing the worst-case growth rate of time or space requirements.
Big-O focuses on the dominant factor as input size (n) approaches infinity, ignoring constants and smaller terms. An algorithm that takes 3n² + 5n + 10 operations is classified as O(n²) because the quadratic term dominates at scale.
Common Complexity Classes
Here are typical complexities from fastest to slowest:
- O(1) – Constant: Array index access
- O(log n) – Logarithmic: Binary search
- O(n) – Linear: Single loop through data
- O(n log n) – Linearithmic: Efficient sorting (merge sort)
- O(n²) – Quadratic: Nested loops
- O(2ⁿ) – Exponential: Recursive fibonacci (naive)
Time vs Space Complexity
Big-O applies to both dimensions:
- Time complexity: How execution time scales
- Space complexity: How memory usage scales
A hash table lookup might be O(1) time but O(n) space. Understanding both helps you make informed trade-offs between speed and memory.
The Scalability Lens
Big-O reveals what happens when your system grows from 100 to 100,000 users. An O(n²) algorithm processing 100 items takes 10,000 operations; at 1,000 items, it takes 1,000,000 operations—a 100× input yields 10,000× work. This makes Big-O essential for predicting production behavior.
Key Takeaway: Big-O notation describes how algorithms scale by expressing the growth rate of resource consumption relative to input size, helping you predict performance at scale and choose appropriate data structures and algorithms.