Big-O — the only complexity vocab you need

Day 15. Week three. We pivot from Python the language to the algorithms and data structures Python the language sits on top of.

Let's start with the question every interviewer asks and most candidates answer badly — 'what's the time complexity?'

Big-O is not math. It's a label that describes how an algorithm's runtime (or memory) grows as the input size grows. That's it. The constants don't matter. The lower-order terms don't matter. We care about the growth pattern, not the exact count.

The six classes you'll meet daily, in order of pain:

O(1) — constant. Doesn't grow with input size. dict lookup. Array indexing. The fastest possible.

O(log n) — logarithmic. Halves the input each step. Binary search. Tree depth in a balanced tree. Doubling input adds one step. Phenomenal scaling.

O(n) — linear. Touches each item once. Scanning a list. Reading a file. Doubling input doubles the work. Acceptable.

O(n log n) — linearithmic. Best general-purpose comparison sort. Mergesort, timsort, heapsort. Doubling input slightly more than doubles the work. Considered efficient.

O(n²) — quadratic. Nested loop over the input. Bubble sort. Naive duplicate check with two for-loops. Doubling input quadruples the work. Painful past 10k elements.

O(2ⁿ) — exponential. Recursive subset enumeration without memoisation. Each new input doubles the entire work. Painful past 30 elements. Almost always fixable with DP.

You don't need to compute exact constants. You need to recognise which family your code falls into. That recognition, applied repeatedly, is the difference between code that scales and code that bricks production.

There's a quick recipe for estimating Big-O that works for 90% of code you'll read, takes about 30 seconds, and you can do it standing up at a whiteboard.

Step one — find the dominant loop. The outermost loop that depends on the input size. Ignore loops with a fixed bound (for i in range(10): doesn't scale with input).

Step two — count how that loop depends on n. One pass over n items? O(n). Nested loop, both over n? O(n²). Halving each step? O(log n).

Step three — figure out the worst single operation inside the loop. Is it a dict lookup (O(1))? A 'in list' check (O(n))? A sorted call (O(n log n))? The whole inner block dominates by its slowest op.

Step four — multiply the loop count by the inner op's complexity.

That's it. Linear-loop-with-constant-inner = O(n). Linear-loop-with-linear-inner = O(n²). Logarithmic-loop-with-constant-inner = O(log n).

The most common Big-O upgrade in real Python — finding 'in list' inside a loop, replacing the list with a set. 'in list' is O(n); 'in set' is O(1). The loop drops a complexity class for free. We see this exact pattern across half the leetcode mediums.

A gotcha — recursive functions. Don't count the recursion explicitly. Count the depth of recursion times the work per call. Fibonacci's naive recursion calls itself twice per step, depth n, so O(2^n). Adding memoisation makes each subproblem solved once, so O(n).

Most code falls into one of the six classes from the morning post. Recognising the family is the skill. Multiplying constants is the math you don't need.

The single most common Big-O upgrade in interview problems and real code is this exact pattern.

The naive duplicate check is two nested loops. For every item, check every other item. O(n²). Slow past 10k elements; unusable past 100k.

The upgrade is one structure swap. Use a set to track items you've seen. As you walk the list, check membership against the set (O(1)) and add the current item (O(1)). One pass. O(n) time. O(n) extra space.

Look at the snippet. Same problem, two solutions, two complexity classes. The fast version is barely longer than the slow one.

Why this matters more than just 'duplicate detection'. The pattern of trading memory for hash lookups appears everywhere:

Two-sum. Naive O(n²) checks all pairs. With a dict mapping value-to-index, one pass O(n).

Group-by. Naive O(n²) puts each item in the right group via linear search. With a defaultdict, one pass O(n).

Finding intersection of two lists. Naive nested-loop O(n*m). Convert one to a set; iterate the other. O(n + m).

Finding the longest substring without repeats. Naive enumerates all substrings. With a sliding window and a set, one pass O(n).

The meta-pattern: when the brute force is 'for each X, for each Y, do something', ask if a hash structure can replace one of the loops with O(1) lookups. The answer is yes more often than not.

This single move, applied thoughtfully, accounts for a huge fraction of leetcode-medium solutions. Internalise it.

There's a reflex among Big-O-aware developers to optimise everything to the lowest possible complexity. Resist it. Big-O is a guide; profiling is the truth.

Big-O describes asymptotic behaviour — what happens when n grows large. For small n, the constants and lower-order terms (which Big-O ignores) often dominate. A 'quadratic' algorithm with a 1ns inner step beats a 'linear' algorithm with a 100ns inner step until n gets pretty large.

Real-world Python performance bugs are usually NOT algorithmic. They're:

I/O — synchronous network calls, disk reads, file opens. Each one takes milliseconds. A loop with 100 sync HTTP calls is slow not because of algorithmic complexity but because of 100 round trips.

JSON parsing — surprisingly expensive on large objects. Python's stdlib json is slow; orjson is 5-10x faster.

String operations — Python strings are immutable. += in a loop is O(n²) total. Use ''.join() — O(n) total.

Global dict lookups — accessing a function in a module's global dict is slower than accessing a local variable. Hot loops sometimes benefit from rebinding to local names.

Unnecessary list materialisation — comprehensions where generators would do, in-memory copies of huge data instead of streaming.

Before you 'optimise' an O(n) loop to O(log n), measure where the actual time goes.

My default tools — cProfile and snakeviz for offline profiling. py-spy for production-style sampling. scalene for combined CPU+memory profiling. Each gives you a different view; each takes 5 minutes to set up.

For algorithmic problems at scale, Big-O wins. For 90% of real Python performance work, the profiler points you at I/O or string ops, not at your algorithm. Measure first.

End of Day 15. Week three begins. Welcome to DSA week.

A quick frame for the next two weeks. We're not doing competitive-programming gymnastics. We're building the vocabulary that turns 'this code is slow' into 'this code is O(n²) because of a nested in-list-check, and the fix is to swap the inner list for a set, dropping it to O(n)'.

That vocabulary is the foundation that makes ML interviews bearable, makes code reviews precise, and lets you read other people's code with a sharper eye.

What we covered today.

Morning — Big-O as a label for growth. Six classes (constant, log, linear, linearithmic, quadratic, exponential) cover almost every algorithm you'll see. Recognise the family; ignore the constants.

Midday — a 30-second estimation recipe. Find the dominant loop, count its dependence on n, multiply by the worst inner op. Works for 90% of code you'll read.

Afternoon — the dedup pattern as the canonical Big-O upgrade. Trade memory for hash lookups. Drop a complexity class. The pattern shows up across most interview mediums.

Evening — measure before you optimise. Big-O is asymptotic; for small n the constants dominate. Real Python perf bugs are usually I/O or string ops. cProfile, snakeviz, py-spy are your friends.

Tomorrow, Day 16, arrays. Python's list is the workhorse. Slicing, two-pointer, prefix sum — the patterns interviewers love and that show up constantly in real ML code (sliding windows in time series, prefix sums in batch normalisation, two-pointer in tokeniser code).

See you in the morning.