The Core Idea
Big-O Measures Growth, Not Speed
Big-O notation does not tell you how many seconds an algorithm takes. It tells you how the number of operations grows as the input size (n) grows. A slow constant-time algorithm on a fast machine can beat a fast-looking algorithm with bad complexity once n gets large enough — that's the entire point of studying this.
Think of Big-O as answering one question: 'If I double my input size, what happens to my runtime?' The answer to that question is the algorithm's true identity, independent of hardware, programming language, or how cleverly you wrote the code.
💡 Memory Trick
Picture six runners on a track, each representing a complexity class. O(1) teleports to the finish line regardless of track length. O(log n) barely slows down even on a mile-long track. O(n) jogs at a steady pace matching the track length exactly. O(n log n) jogs slightly slower than steady. O(n²) crawls, getting exponentially slower as the track lengthens. O(2ⁿ) never finishes a long track in your lifetime.
The Six Classes
Walking the Hierarchy Rung by Rung
O(1)
Constant Time
The operation count never changes, no matter how big the input gets. Accessing an array element by index, checking if a number is even, or pushing onto a stack are all O(1) — one operation whether the array has 10 or 10 million elements.
Example: arr[5] takes the same time whether arr has 6 elements or 6 billion.
O(log n)
Logarithmic Time
Each step cuts the remaining work in half. Binary search is the textbook example — every comparison eliminates half of what's left to check, so doubling the input only adds one extra step.
Example: searching 1,000,000 sorted items takes about 20 steps, not 1,000,000.
O(n)
Linear Time
Work grows exactly in proportion to input size. A single loop through an array — checking each element once, summing a list, finding the maximum value — is O(n). Double the input, double the work.
Example: printing every item in a list of n items requires n print operations.
O(n log n)
Linearithmic Time
The sweet spot for efficient sorting. You do roughly n 'rounds' of work, and each round costs log n because it involves a halving/merging step. Merge sort and quicksort (average case) live here — this is the best general-purpose sorting complexity achievable by comparison-based algorithms.
Example: merge sort splits n items in half repeatedly (log n levels), doing n work to merge at each level.
O(n²)
Quadratic Time
A loop nested inside another loop over the same data — comparing every element to every other element. Bubble sort, selection sort, and insertion sort are O(n²): for each of n items, you scan roughly n other items.
Example: checking every pair in a list of 1,000 items means roughly 1,000,000 comparisons.
O(2ⁿ)
Exponential Time
Work doubles with every single additional input item. This shows up in brute-force recursive solutions that try every possible subset or combination, like naive recursive Fibonacci or the naive traveling salesman solution. It becomes computationally impossible past small n.
Example: at n=30, O(2ⁿ) is already over 1 billion operations; at n=50, it exceeds a quadrillion.
Why It Matters
The Same Problem, Wildly Different Costs
The reason Big-O dominates technical interviews and system design is that at real-world scale, complexity class matters more than any other factor. An O(n²) algorithm on 10 items beats an O(n log n) algorithm because constants matter at small scale — but flip that to n = 1,000,000 and the O(n²) algorithm may take hours while the O(n log n) algorithm finishes in under a second.
This is why engineers ask 'what's the Big-O' before they ask 'is the code clean' — a beautifully written O(n²) solution will still fall over in production the moment the dataset grows past what fits on one screen.
🖥️ Applied Scenario
You're building a search feature for an app with 2 million user records, and you're deciding between two implementations a teammate proposes.
1
Option A scans every record checking for a match — this is O(n), so worst case it checks all 2 million records.
2
Option B first sorts the records once, then uses binary search for every lookup — the search itself is O(log n), meaning roughly 21 comparisons per lookup regardless of dataset size.
3
You recognize that if the search happens thousands of times (e.g., every user typing in a search bar), the O(log n) cost per lookup makes Option B dramatically cheaper over time, even though sorting up front costs extra work once.
4
Conclusion: you choose based on complexity class, not on which code 'looks' faster — this is exactly the judgment Big-O analysis trains you to make.
📌 Exam Application
Exam and interview questions often show you a snippet of code with nested loops, recursion, or a single pass, and ask you to state its Big-O. The fastest way to identify it: count the loops. One loop through n items = O(n). A loop inside a loop over the same n items = O(n²). Any point where the problem size gets cut in half each step (not just iterated) signals O(log n). If the function calls itself twice for every one call (like naive Fibonacci), that's your O(2ⁿ) signal.
⚠️ Most Common Big-O Complexity Hierarchy Mistakes
The most common mistake is confusing O(log n) with O(n) because both 'depend on n' — remember that O(log n) barely grows at all as n gets huge, while O(n) grows in direct proportion. Another common trap: assuming nested loops always mean O(n²) — if the inner loop's range shrinks each time (like in some triangular-pattern algorithms), the true complexity may be lower. Always check what each loop actually iterates over, not just how many loops there are.
✓ Quick Self-Test
Can you rank O(n²), O(1), O(log n), O(n log n), O(2ⁿ), and O(n) from fastest-growing to slowest-growing without looking? Can you name one real algorithm for each class and explain, in one sentence, why it belongs there?