Big-O Notation: How Fast Is Your Code?
Every algorithm you will ever write has a cost: time to run and memory to hold its data. Big-O notation is the language programmers use to describe that cost, and it is the single most common topic in technical interviews. In this lesson you will learn to read Big-O, measure it in real Python code, and recognize the handful of complexity classes that cover almost everything you will meet in practice.
What You'll Learn
- What Big-O notation actually measures (and what it ignores)
- The common complexity classes: O(1), O(log n), O(n), O(n log n), O(n^2)
- How to analyze a Python function line by line
- How to time real code and watch complexity appear in the numbers
Why We Need Big-O
Suppose two functions both find the largest number in a list. One checks every element once. The other compares every element with every other element. Both give the right answer, but on a list of one million items the first does one million steps and the second does one trillion. Big-O captures that difference without caring about your laptop's speed.
Big-O describes how the number of steps grows as the input grows. Constants and small terms are dropped: an algorithm doing 3n + 5 steps is simply O(n), because for large inputs the n dominates.
The Common Complexity Classes
| Big-O | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing my_list[3] |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Scanning a list once |
| O(n log n) | Linearithmic | Merge sort, Python's sorted() |
| O(n^2) | Quadratic | Comparing all pairs, bubble sort |
| O(2^n) | Exponential | Naive recursive Fibonacci |
Run the code below to see how quickly these grow apart:
At n = 10000, an O(log n) algorithm does about 13 steps while an O(n^2) algorithm does 100 million. That gap is why complexity matters more than any micro-optimization.
Analyzing Code: Count the Loops
The practical skill is reading a function and spotting how work scales with input size:
Rules of thumb:
- A single loop over the input is O(n)
- A loop inside a loop over the same input is O(n^2)
- Halving the problem each step (binary search) is O(log n)
- Doing O(n) work at each of O(log n) levels (merge sort) is O(n log n)
- Sequential blocks add, and you keep only the biggest term: O(n) followed by O(n^2) is O(n^2)
Watch Complexity in Real Timings
Theory is nice, but you can measure it. This experiment times a linear and a quadratic duplicate-checker as the input doubles. Open it fullscreen with the expand button and experiment with the sizes:
Notice the pattern: when n doubles, the quadratic time roughly quadruples while the linear time roughly doubles. That is Big-O showing up in real milliseconds, and it is the same trade you will make again and again in this course: a smarter data structure (here, a set) turns O(n^2) into O(n).
Space Complexity
Big-O also describes memory. has_dup_quadratic uses O(1) extra space (just two loop counters), while has_dup_linear uses O(n) extra space for the set. Trading memory for speed is one of the most common patterns in algorithm design.
Exercises
Key Takeaways
- Big-O describes how running time or memory grows with input size, ignoring constants
- The classes to know: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n)
- Nested loops over the same input usually mean O(n^2); one pass means O(n)
- Choosing a better data structure (like a set for membership tests) often improves the complexity class itself
- Space complexity matters too, and trading memory for speed is a standard technique