Data Structures & Algorithms
Big O Notation
Big O notation describes how the resources an algorithm uses, usually time, sometimes memory, grow as the size of its input grows, expressed as an upper bound on that growth rate rather than an exact count of operations. It deliberately ignores constant factors and lower-order terms, because those depend on the specific machine and implementation, and focuses on the shape of growth as input size, conventionally called n, gets large. It is a tool for comparing how two algorithms scale, not a stopwatch measurement of either one.
Why it matters
- Lets you predict whether code that works on 100 items will still work on 10 million
- Code that is fine in a demo with a handful of rows can become unusable at real scale if its growth rate is quadratic instead of linear, and Big-O is what tells you that ahead of time.
- It is a standard shorthand in technical interviews and design discussions
- Explaining the time complexity of a solution is one of the most frequently asked follow-up questions once working code is on the table, so fluency has direct practical value.
- It distinguishes algorithms that look similar in code but scale very differently
- A single loop and a loop nested inside another loop can look like a small code difference but describe a linear versus a quadratic growth rate.
- It explains why certain data structures are chosen over others at scale
- Reaching for a hash table instead of scanning a list is a Big-O argument, average-case constant-time lookup against linear-time scanning, made concrete.
What n and 'growth rate' actually mean
n stands for the size of the input - the length of a list, the number of rows, the number of nodes in a graph. Big-O asks how the number of operations an algorithm performs grows as n grows, not how many operations it performs for one specific n. A loop that touches each of n items once does roughly n units of work: at n = 10 that is about 10 operations, at n = 1,000 it is about 1,000 - the work grows in direct proportion to n. A loop nested inside another loop, each running roughly n times, does roughly n times n units of work: at n = 10 that is about 100 operations, but at n = 1,000 it is about 1,000,000 - the gap between the two grows very fast, even though both looked like just a couple of loops in the code.
n = 1000
# roughly n operations
for i in range(n):
pass
# roughly n * n operations
for i in range(n):
for j in range(n):
passThe common complexity classes, from cheapest to most expensive
O(1), constant time, means the work does not depend on n at all - looking up a value by index in an array. O(log n), logarithmic, means the work barely grows as n grows because each step eliminates a large fraction of the remaining possibilities - binary search on a sorted list. O(n), linear, means the work grows in direct proportion to n - a single pass over a list. O(n log n) is what most good general-purpose sorting algorithms achieve - more than linear, but far below quadratic. O(n squared), quadratic, means the work grows with the square of n - a nested loop comparing every pair of items. Beyond that, exponential growth, roughly 2 raised to the power of n, shows up in some brute-force approaches and becomes impractical very quickly as n grows past a small number.
Mistakes people make here
- Treating Big-O as an exact runtime prediction rather than a growth-rate bound
- Two algorithms both described as O(n) can run at very different real speeds, because Big-O deliberately drops the constant factor in front of n - one might do one unit of work per item, another might do fifty.
- Missing a hidden loop inside what looks like a constant-time check
- A membership check against a plain list looks like one operation in the code, but it is actually a linear scan under the hood - the cost is just hidden behind the syntax, not absent.
- Confusing best-case behavior with worst-case behavior
- An algorithm can behave very differently depending on the input it receives - quicksort is commonly described as O(n log n) but has a real O(n squared) worst case on certain input orderings, and conflating the two gives a false sense of a guarantee that is not actually there.
- Only counting time and ignoring space
- An algorithm can trade memory for speed, or vice versa, and in practice, memory usage is sometimes the actual constraint long before the time complexity becomes the bottleneck.
Strengths and trade-offs
Where it is strong
- Gives a common vocabulary to compare two algorithms without having to actually run either one.
- Predicts real behavior at large n reliably, even though it says very little about small n.
- Makes it possible to reason about a data structure's cost before a single line of the implementation exists.
The trade-offs
- Says nothing about constant factors, so a theoretically worse O(n log n) algorithm with a small constant can beat a theoretically better O(n) one for realistic input sizes.
- Worst-case Big-O can be needlessly pessimistic for algorithms that are fast on typical, non-adversarial input, which is a real gap between the notation and everyday performance.
- Says nothing about real hardware effects like CPU cache behavior, which frequently matter more than the asymptotic class for the input sizes most programs actually see.
Who needs this
Anyone comparing algorithms or choosing between data structures at a scale where the choice actually matters, and effectively required knowledge for technical interviews. For a one-off script running once over fifty rows, it honestly makes little practical difference.
Questions about big o notation
- Does a smaller Big-O always mean faster in practice?
- No. Big-O describes how cost grows as input grows, not the actual cost at any one input size, and it ignores constant factors. A theoretically worse algorithm with a small constant factor can outperform a theoretically better one until n gets fairly large.
- What's the intuitive difference between O(n) and O(n log n)?
- O(n) does roughly one unit of work per item. O(n log n) does roughly one unit of work per item, log n times over - in practice, for a sort, that means each item participates in roughly log n comparisons as the data gets progressively divided and merged, rather than just being touched once.
- Is Big-O about time or about memory?
- Either - it is a general notation for describing growth, and can describe time complexity or space complexity, or both for the same algorithm. Which one is meant is usually clear from context, but it is worth stating explicitly when it might not be.
- If Big-O doesn't predict exact runtime, why do interviewers ask about it so much?
- Because it demonstrates that a candidate can reason about how a solution will behave beyond the specific example in front of them, whether an approach that works on a small test case will still work when the input is realistically large, which is exactly the judgment that matters once code ships.