Understanding Algorithmic Complexity (Big O)
You'll learn how to describe and compare the performance characteristics of different algorithms using Big O notation.
What Is Big O?
Big O notation describes how an algorithm's runtime or memory usage grows as the input size increases. It's not about measuring seconds or milliseconds—it's about understanding scalability. Does your function take twice as long when you double the data? Ten times as long? A hundred times?
Think of it like planning a party: counting guests takes O(n) time—one count per person. Checking if everyone has shaken hands with everyone else? That's O(n²)—much slower as the guest list grows.
The Three Most Common Complexities
O(1) - Constant Time
Performance doesn't change with input size. Accessing an array by index or looking up an object property: always fast, whether you have 10 items or 10 million.
O(n) - Linear Time
Performance grows directly with input size. A single loop through an array: double the elements, double the time. This is often acceptable and unavoidable.
O(n²) - Quadratic Time
Performance grows with the square of input size. Nested loops where each processes all items: double the input, quadruple the time. This becomes painfully slow with large datasets.
Why It Matters
Clever code tricks like variable caching or avoiding function calls might save microseconds. But choosing an O(n) algorithm over an O(n²) one can save hours on large datasets. Algorithm choice is architectural—it changes the fundamental shape of your performance curve.
Key Takeaway: Big O describes how performance scales with input size—O(1) stays constant, O(n) grows linearly, O(n²) grows quadratically. Choosing the right algorithm matters far more than micro-optimizations.