How Complexity Works — Big-O and the Cost of Scale

An algorithm that works on 100 items might be fast. The same algorithm on 10 million items might take hours — or years. Complexity analysis (Big-O notation) tells you how an algorithm's resource usage grows as the input size grows, without running it.

This is the single most important tool for predicting whether code will scale.

What Does Big-O Mean?

Big-O describes the upper bound of growth rate. O(n) means the time grows at most linearly with input size. O(n²) means at most quadratically. The notation ignores constants and lower-order terms — it captures the shape of the growth, not the exact time.

Why ignore constants? Because at scale, the growth rate dominates. An O(n) algorithm with a large constant will always eventually beat an O(n²) algorithm with a tiny constant — you just need enough data.

The Common Complexities

Complexity	Name	Example	1,000 items	1,000,000 items
O(1)	Constant	Hash map lookup	1 op	1 op
O(log n)	Logarithmic	Binary search	10 ops	20 ops
O(n)	Linear	Scan an array	1,000 ops	1,000,000 ops
O(n log n)	Linearithmic	Merge sort	10,000 ops	20,000,000 ops
O(n²)	Quadratic	Nested loops	1,000,000 ops	1,000,000,000,000 ops
O(2^n)	Exponential	Brute-force subsets	10^301 ops	impossible

The jump from O(n) to O(n²) is the difference between "takes a second" and "takes 11 days" at a million items. The jump from O(n²) to O(2^n) is the difference between "takes 11 days" and "outlasts the universe."

O(1) — Constant Time

The operation takes the same time regardless of input size. Array access by index (arr[5]), hash map lookup, pushing onto a stack.

Not all O(1) operations are fast in absolute terms. A hash map lookup involves hashing, bucket selection, and comparison — maybe 100 nanoseconds. But it's the same 100 nanoseconds whether the map has 10 entries or 10 million.

O(log n) — Logarithmic

Each step eliminates half the remaining data. Binary search is the classic example: look at the middle element, discard the half that can't contain your target, repeat.

Searching a sorted array of 1 billion elements: log₂(1,000,000,000) ≈ 30 steps. Not 1 billion steps — 30.

B-trees in databases use this principle. An index lookup in PostgreSQL traverses a tree of height 3-4, regardless of whether the table has 1,000 or 1 billion rows. This is why database indexes matter.

O(n) — Linear

You look at every item once. Scanning an unsorted array, summing a list, reading a file. If the data doubles, the time doubles.

Linear time is often the best you can do when you need to see every item. You can't find the maximum of an unsorted array without looking at everything. But if you're scanning when you could be doing a lookup, that's a performance bug.

O(n log n) — Linearithmic

The sweet spot for sorting. Merge sort, quicksort (average case), and heap sort all achieve O(n log n). You can't sort by comparison faster than this — it's proven mathematically.

This is why sorting a million items takes ~20 million operations (fast) and not a trillion (O(n²) naive sort). The gap matters enormously in practice.

O(n²) — Quadratic

Nested loops where each item is compared against every other item. Bubble sort, checking all pairs, naive string matching.

O(n²) is manageable for small data (1,000 items = 1 million operations). At 1 million items, it's 1 trillion operations — hours or days of computation. This is the complexity that catches people: it works in development (small data) and fails in production (real data).

How Do You Determine Complexity?

Count the loops:

• One loop over n items → O(n)
• Two nested loops over n items → O(n²)
• Loop that halves the data each step → O(log n)
• Sort followed by a scan → O(n log n) + O(n) = O(n log n)

Drop constants and lower-order terms:

• O(3n + 5) → O(n)
• O(n² + n) → O(n²)
• O(100) → O(1)

Take the dominant term:

• O(n² + n log n) → O(n²) — the n² dwarfs everything else at scale.

Time vs Space Complexity

Big-O applies to both time (how many operations) and space (how much memory).

A hash map gives O(1) lookup time but uses O(n) space. Sorting in-place (quicksort) uses O(1) extra space but O(n log n) time. Merge sort uses O(n) extra space.

The tradeoff between time and space is one of the most fundamental decisions in engineering. Caching trades space for time. Compression trades time for space. Inverted indexes trade space for lookup speed. HNSW vector indexes trade 2x memory for O(log n) search.

Where Does Complexity Show Up?

Database queries — a full table scan is O(n). An indexed lookup is O(log n). Adding an index is the difference between a query taking 5 seconds and 5 milliseconds. This is why EXPLAIN exists.

Search — BM25 with an inverted index is O(k) where k is the number of documents containing the query terms — not O(n) over all documents. That's the entire point of the index.

Networking — DNS caching is O(1) lookup vs O(hierarchy depth) resolution. Connection pools avoid O(handshake) per request.

API design — returning all items vs paginated results. O(n) response size vs O(page_size). Pagination is a complexity decision.

Next Steps

• How Character Encoding Works — how text is represented as numbers.
• Data Structures — arrays, hash maps, trees — each with different complexity tradeoffs.
• Algorithms — sorting, searching, and graph algorithms analyzed by complexity.