Big O Without the Hand-Waving: Reasoning About Growing Inputs

Introduction

Big O is a way to describe what happens to an algorithm when its input becomes larger. For example, an operation that checks every item will usually take more work when more items are added. The first question is not “which formula do I use?” but “what work grows when I add more items?”

Big O started making more sense to me when I stopped treating it as a label attached to an entire piece of code. A statement such as “this is O(n)” is incomplete until I can answer three questions:

1. What operation am I counting?
2. What does n represent?
3. Is this a worst-case, average-case, expected, or amortized claim?

Big O describes the general growth of a cost as the input becomes larger. This is called asymptotic analysis. It does not tell us the exact number of milliseconds a program will take, and it does not make constants, hardware, runtimes, or data layout irrelevant.

This article uses operations that appear across the data-structure learning series—linked-list traversal, hash-table lookup, binary-search-tree search, and merge sort. The costs here describe the standard algorithms and their stated assumptions. Later repository-backed articles must still inspect the actual implementations before assigning costs to particular methods.

What the notation means

The letter n is a placeholder for the size of the input. If n means “the number of routes,” then O(n) means that the amount of work grows roughly with the number of routes. It does not mean that the program will take exactly n milliseconds or execute exactly n instructions.

Here is a practical comparison:

• If a task checks every item once, doubling the items usually means about twice the work. We call that linear, written O(n).
• If a task compares every item with every other item, doubling the items can mean about four times the work. We call that quadratic, written O(n²).
• If a task keeps cutting the remaining problem in half, the number of steps grows slowly. We call that logarithmic, written O(log n).

The notation is a compact label for these growth patterns. The formal definition in MIT OpenCourseWare's algorithms material explains Big O as an upper bound once the input is large enough. For this article, the practical reading is enough: it tells us how the work changes when the input grows.

For example, a loop that performs 3n + 20 simple operations is still described as O(n). The 3 and 20 matter for real inputs, but they do not change the fact that the work grows in a straight line.

You may also see Θ(n). Read it as “grows like n” when both an upper and lower growth bound are known. Many developers use Big O as a general term for complexity, but the important beginner habit is to explain the growth in words first.

Common growth patterns

The table assumes one input size, called n, so the patterns can be compared. The entries describe how the work grows; they are not exact execution times.

When an algorithm repeatedly halves a problem, the number of steps is usually described as logarithmic. The exact base of the logarithm is not important for this comparison because changing the base only changes the result by a constant factor.

Big O is not a stopwatch

Consider two linear cost functions:

A(n) = 2n
B(n) = 100n

Both grow linearly, so both are written as Θ(n). However, B performs fifty times as many counted operations in this simplified model. Now compare:

B(n) = 100n
C(n) = n²

For small n, C may perform less work than B. At n = 10, the simplified counts are 100 for C and 1,000 for B. They become equal at n = 100; above that point, the quadratic term exceeds 100n and then pulls away increasingly quickly.

This is why asymptotic analysis and measurement answer different questions:

• asymptotic analysis asks how growth behaves as input size increases;
• benchmarking measures a particular implementation, runtime, machine, dataset, and experimental setup.

Cache locality, allocation, interpreter or JIT behaviour, compiler optimization, branch prediction, and constant overhead can all change real timings without changing the growth class. An array scan can outperform a theoretically logarithmic structure at small sizes because contiguous storage and simple operations have favorable constants.

That observation does not disprove Big O. It means Big O was never intended to be an exact timing model.

No benchmark is presented in this article. A defensible benchmark would need its script, runtime version, hardware context, input-generation method, warm-up procedure, sample counts, and limitations.

Name the input being measured

The letter n has no universal meaning. It must be defined for the operation under discussion.

For linked-list traversal, n can mean the number of nodes. For hashing a string key, a more complete analysis may use k for key length and n for the number of stored entries. Computing the hash is then at least related to k, even if locating a well-distributed bucket is expected to be constant with respect to n.

For a binary search tree, search is most directly expressed in terms of height:

O(h)

If a tree with n nodes is balanced, h is O(log n). If its nodes form a chain, h is O(n). Saying only “BST search is O(log n)” silently assumes a shape that an ordinary, non-self-balancing BST does not guarantee.

Multiple independent inputs should remain visible. If a program compares every user with every permission, the cost is:

Θ(users × permissions) = Θ(nm)

It becomes Θ(n²) only under an assumption that both collection sizes grow together and are represented by the same variable.

Two nested loops are not automatically O(n²)

This loop nest performs three inner operations for each of n items:

for (let item = 0; item < n; item += 1) {
  for (let attempt = 0; attempt < 3; attempt += 1) {
    check(item, attempt);
  }
}

The operation count is approximately 3n, so the growth is Θ(n). The inner bound is a constant, not n.

Now compare all distinct pairs:

for (let first = 0; first < n; first += 1) {
  for (let second = first + 1; second < n; second += 1) {
    compare(first, second);
  }
}

The inner loop does not run n times on every iteration. It runs n - 1, then n - 2, continuing down to zero. The total is:

(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2

That is Θ(n²). The conclusion comes from summing the iteration counts, not merely seeing two loops.

A third pattern can still be linear even when loops are nested:

let end = 0;

for (let start = 0; start < n; start += 1) {
  while (end < n && shouldAdvance(start, end)) {
    end += 1;
  }
}

If end never moves backward, the while body can execute at most n times over the entire run, not n times for each outer iteration. The outer loop is linear and the total inner work is linear, giving Θ(n) work apart from the cost of shouldAdvance.

Four data-structure examples

The standard bounds below are useful only with their assumptions attached.

These are design-level costs. A repository may store no tail, use a particular collision strategy, reject duplicate BST values, or implement merging with operations that introduce additional work. Each project article should derive its table from the code rather than copying this one blindly.

The analyses in Open Data Structures repeatedly connect operation bounds to representation choices. That connection matters more than memorizing a list of labels.

Worst-case, average-case, expected, and amortized

These terms answer different questions and should not be used interchangeably.

Worst-case

Worst-case complexity gives an upper bound over all allowed inputs of a given size. Searching an ordinary BST with n nodes is O(n) in the worst case because the tree can become a chain.

Worst-case analysis is useful when latency guarantees matter or adversarial inputs are possible. It does not claim that every operation takes the maximum amount of work.

Average-case

Average-case complexity averages over a stated probability distribution of inputs. It is incomplete to say “average O(log n)” without explaining what tree shapes or insertion orders are considered likely.

Real-world input is not automatically uniform or random. Sorted insertion into an ordinary BST, for example, can consistently produce a skewed shape rather than an average-looking one.

Expected

Expected complexity commonly averages over random choices made by an algorithm or data structure, sometimes for a fixed input. Hash-table analyses may use assumptions about randomized or sufficiently uniform hashing to justify expected constant bucket work.

“Expected O(1) lookup” is therefore more careful than “hash maps are always O(1).” It still needs assumptions about hashing, load factor, collision handling, and the cost of processing the key.

Amortized

Amortized analysis spreads occasional expensive operations across a sequence of operations. It does not require randomness.

A growable array may append in constant time until it runs out of capacity. A resize then allocates larger storage and copies many existing elements, so that one append is O(n). If capacity grows geometrically, those expensive copies occur infrequently enough that a sequence of appends has O(1) amortized cost per append.

Hash-table insertion can have the same pattern: most insertions are small operations, while a resize may rehash all entries. Calling every insertion individually O(1) hides that spike; calling insertion amortized expected O(1) states both the resizing and hashing assumptions more honestly.

Balanced and unbalanced BST search

A binary search tree demonstrates why structure shape belongs in a complexity claim. Search compares at the current node and then chooses at most one child, so its cost follows the length of one root-to-node path.

For a balanced tree containing about one million nodes, a path may be around twenty levels because 2²⁰ is just over one million. Doubling the number of nodes adds roughly one level.

For a skewed tree, each node may have only a right child. Searching for the last value then visits every node, behaving like a linked-list traversal. The ordering invariant still holds, but the shape no longer provides logarithmic height.

This yields the precise progression:

search cost = O(h)
balanced height h = O(log n)
skewed height h = O(n)

A self-balancing tree can guarantee logarithmic height through additional rules and rotations. An ordinary learning-project BST should not be described as having that guarantee unless its implementation actually maintains one.

Hash maps: expected does not mean guaranteed

Hash maps turn a key into a hash and then a bucket index. With a suitable hash function, controlled load factor, and effective collision handling, keys remain distributed enough that the expected number of entries examined per lookup stays bounded.

Several costs are hidden by the shorthand “expected O(1)”:

• hashing a key takes work, often proportional to the amount of key data examined;
• distinct keys can map to the same bucket;
• a poor distribution can make one bucket long;
• resizing may require every stored entry to be rehashed; and
• an adversary may deliberately choose colliding keys when the hash behaviour is predictable.

The worst-case lookup for separate chaining is linear in the number of entries if they all land in one chain. The expected bound remains useful, but only when stated alongside the conditions that support it.

Merge sort: counting levels and work per level

The previous article followed merge sort's recursion. In a more formal textbook, the work may be written as a recurrence. You do not need that formula to use the main idea: sort two smaller halves, then do one pass of merge work over the current values. There are about log n levels, and each level processes about n values, so the usual shorthand is O(n log n).

Implementation choices still matter. Repeatedly removing the first element of a JavaScript array can add shifting work that an abstract constant-time “take next item” step does not include. Big O analysis must count the operations actually used, not the pseudocode operation we intended them to represent.

Space complexity is a separate question

Time complexity is only one resource measure. Merge sort commonly uses Θ(n) auxiliary array space plus a logarithmic recursion stack. A linked list uses additional storage for a reference in every node. A hash table deliberately keeps spare capacity to control its load factor.

An algorithm with better time growth may use more memory, and an in-place algorithm may accept additional computation to reduce auxiliary storage. A useful analysis names the resource:

Time:  Θ(n log n)
Space: Θ(n)

Without that label, a standalone O(n) can be misunderstood.

A checklist for making a complexity claim

Before writing a Big O label, ask:

1. What is the operation or algorithm being analyzed?
2. What does each input variable represent?
3. What elementary work am I counting?
4. Do called operations such as slicing, hashing, or front removal have their own cost?
5. Is the result a worst-case, average-case, expected, or amortized bound?
6. What representation or input-distribution assumptions support it?
7. Am I describing time, auxiliary space, or another resource?
8. Is Big O sufficient, or do I know a tighter Θ bound?

This turns complexity analysis from label memorization into an explanation that another developer can inspect and challenge.

Key takeaways

• Big O is an asymptotic upper bound, not an exact runtime measurement.
• Θ is more informative when both an asymptotic upper and lower bound are known.
• Constants and hardware still affect practical performance for finite inputs.
• Always define what n measures; multiple independent inputs may require expressions such as O(nm).
• Nested loops are not automatically quadratic—count how many times their bodies can run.
• Linked-list operations depend on traversal and whether references such as a tail are stored.
• Hash-map lookup is expected constant time only under stated hashing and load assumptions; its worst case can be linear.
• BST search is O(h): logarithmic for a balanced shape and linear for a fully skewed one.
• Amortized cost spreads occasional expensive work across an operation sequence and does not mean average-case or randomized.
• Time and auxiliary-space complexity should be reported separately.

Sources

• MIT OpenCourseWare: Asymptotic notation, recurrences, substitution, and the master method
• Thomas H. Cormen et al., Introduction to Algorithms, fourth edition
• Open Data Structures