Every algorithm is
fast enough
until it isn't.

Appending writes one slot — constant. When the array is full it allocates a bigger one and copies everything, which is n. Doubling the capacity means that copy happens on the 1st, 2nd, 4th, 8th… append, so n appends copy 1 + 2 + 4 + … + n < 2n elements in total. Spread over n appends that is a constant each: amortised O(1).

append(a, x):
  if a.len == a.cap:
    bigger = allocate(2 * a.cap)
    copy(a.items → bigger)      # n, but rarely
    a.items = bigger
  a.items[a.len] = x            # 1, almost always
  a.len += 1

The marked lines are where the cost lives.

Growing by a fixed amount instead of a factor turns the same loop quadratic: n/c copies of average size n/2. The doubling is not an implementation detail, it is the bound.

Each comparison throws away half of what is left, so the number of steps is how many times you can halve n before reaching one — log₂ n. A million elements is twenty comparisons; a billion is thirty.

search(a, x):
  lo, hi = 0, a.len - 1
  while lo <= hi:
    mid = (lo + hi) / 2
    if a[mid] == x: return mid
    if a[mid] < x: lo = mid + 1   # half gone
    else:           hi = mid - 1  # half gone
  return not_found

The marked lines are where the cost lives.

The halving depends on reaching a[mid] in constant time. On a linked list, or on a sorted file you must seek through, the trick evaporates.

There is no arithmetic that turns an index into an address, so reaching element k means following k pointers. Splicing, by contrast, rewrites two fields — but only once you are already standing at the right node.

insert_after(node, x):
  fresh = Node(x)
  fresh.next = node.next   # 1
  node.next = fresh        # 1
 
get(head, k):
  for i in 0..k: head = head.next   # k pointer hops

The marked lines are where the cost lives.

The famous O(1) insert is priced without the search. Insert "after the value 42" costs O(n) — the walk, not the write.

A back pointer means a node knows both of its neighbours, so it can unlink itself without anyone finding its predecessor first. That is the whole difference, and it is what makes O(1) removal possible.

unlink(node):
  node.prev.next = node.next   # 1
  node.next.prev = node.prev   # 1
  # no search: the node knew both sides

The marked lines are where the cost lives.

It only pays when something else hands you the node. An LRU cache works because a hash map maps key → node; without that map you are back to scanning.

Everything happens at one end of an array: write at len, read at len − 1. No element ever moves, so every operation is a couple of instructions — apart from the occasional resize, which amortises away exactly as it does for an array list.

push(s, x): s.items[s.len] = x; s.len += 1
pop(s):     s.len -= 1; return s.items[s.len]
peek(s):    return s.items[s.len - 1]

The marked lines are where the cost lives.

Searching a stack is O(n) and destroys the abstraction. If you find yourself searching one, you wanted a different structure.

Two indices — head and tail — chase each other around a fixed-size ring. Enqueue writes at tail, dequeue reads at head, and neither shifts anything, so both are constant.

enqueue(q, x):
  q.items[q.tail] = x
  q.tail = (q.tail + 1) % q.cap   # wrap, not shift
 
dequeue(q):
  x = q.items[q.head]
  q.head = (q.head + 1) % q.cap
  return x

The marked lines are where the cost lives.

Implementing dequeue as "remove the first element of an array" shifts every remaining element and makes it O(n). The modulo is what buys the constant.

The same ring trick, but both ends are live: push and pop at head or tail are index updates. Indexing into the middle is still constant when the deque is one array, and one extra indirection when it is a list of blocks.

push_front(q, x):
  q.head = (q.head - 1) % q.cap
  q.items[q.head] = x
 
push_back(q, x):
  q.items[q.tail] = x
  q.tail = (q.tail + 1) % q.cap

The marked lines are where the cost lives.

Inserting in the middle is O(n) — a deque is fast at its ends and ordinary everywhere else.

The hash turns a key into a bucket index in constant time, so lookup is one array access plus a walk of that bucket. With n keys in m buckets and a hash that spreads well, the average chain is n/m — kept under a small constant by resizing, which is why the average is O(1). The worst case is every key in one bucket: a linear scan.

lookup(t, key):
  i = hash(key) % t.buckets.len   # 1
  for entry in t.buckets[i]:      # chain length
    if entry.key == key: return entry.value
  return missing

The marked lines are where the cost lives.

Iteration order is not insertion order and may differ between runs. Depending on it is a bug that survives every test until it does not.

No chains: a collision probes the next slot, and the next, until it finds an empty one. While the table is under about 70% full the expected probe count is a small constant, and every probe is the next cache line rather than a pointer dereference. As the load factor approaches 1 the probe runs merge and the constant explodes.

lookup(t, key):
  i = hash(key) % t.cap
  while t.slots[i] is not empty:   # probe run
    if t.slots[i].key == key: return t.slots[i].value
    i = (i + 1) % t.cap
  return missing

The marked lines are where the cost lives.

Deleting cannot just blank a slot — that would cut a probe run in half and hide later keys. Tombstones accumulate and are cleaned only by a rehash.

Every comparison sends you down one side, so a search costs one step per level. On a balanced tree there are log n levels. Nothing in a plain BST enforces balance, though: the height is whatever the insertion order made it, up to n.

search(node, x):
  while node:
    if x == node.key: return node
    node = x < node.key ? node.left : node.right
  # cost = the height of the tree, not log n

The marked lines are where the cost lives.

Inserting already-sorted data — a common case, since data often arrives sorted — builds a path, not a tree. Every operation becomes O(n).

The heights of any node's two subtrees differ by at most one. That invariant forces the height to at most about 1.44 log n, so every operation is logarithmic in the worst case, not merely on average. A rotation is a constant-time pointer rewrite that restores the invariant after a write.

insert(node, x):
  node = bst_insert(node, x)      # log n
  update_height(node)
  if balance(node) > 1:
    node = rotate(node)           # 1
  return node

The marked lines are where the cost lives.

A delete can trigger rotations all the way back to the root — up to log n of them — where an insert needs at most one.

Colour rules keep every root-to-leaf path within a factor of two of every other, so the height is at most 2 log n. That is a weaker guarantee than AVL, bought back as fewer rotations per update — at most three on insert, and O(1) amortised overall.

insert(t, x):
  n = bst_insert(t, x); n.colour = RED
  while n.parent is RED:
    recolour or rotate(n)   # ≤ 3 rotations, ever
    n = n.grandparent
  t.root.colour = BLACK

The marked lines are where the cost lives.

Slightly taller than an AVL tree, so lookup-dominated workloads do measurably more comparisons. This is the trade the standard libraries chose.

A node holds B keys rather than one, so the tree is log_B n deep instead of log₂ n. Comparisons inside a node are free relative to the read that fetched it, and that read brought back a whole block — which is the entire point on a device where a random read costs a millisecond.

search(node, key):
  while node is internal:
    i = binary_search(node.keys, key)  # in RAM, free
    node = read_block(node.child[i])   # one disk read
  return node.find(key)
  # depth = log_B n ≈ 4 for a billion keys

The marked lines are where the cost lives.

In memory it loses to a binary tree: the wide nodes exist to amortise a block read that is not happening.

Each node is promoted to the next level with probability ½, so level k holds about n/2^k nodes and there are about log n levels. A search walks forward on a sparse level until it would overshoot, then drops — an expected constant number of steps per level.

search(list, key):
  node = list.head
  for level from top down to 0:
    while node.next[level].key < key:
      node = node.next[level]   # ~2 steps expected
  return node.next[0]

The marked lines are where the cost lives.

Expected, not guaranteed: a run of unlucky coin flips can build a tall thin list. In exchange, updates touch a few pointers with no global rebalancing — the reason concurrent maps favour it.

Lookup follows one child pointer per character of the key, so the cost is m — the key length — and does not depend on how many keys are stored. A prefix query walks m characters and then enumerates whatever hangs below.

search(root, word):
  node = root
  for ch in word:            # m steps, whatever n is
    node = node.children[ch]
    if not node: return false
  return node.is_word

The marked lines are where the cost lives.

An array of child pointers per node is the alphabet size times a word, per character stored. Memory, not time, is what kills naive tries.

The array is covered by a binary tree of ranges. Any query range decomposes into at most two nodes per level — about 2 log n nodes — whose stored answers combine into the result. An update rewrites one leaf and the log n ancestors above it.

query(node, lo, hi):
  if node.range inside [lo,hi]: return node.value
  if node.range misses [lo,hi]: return identity
  return combine(query(node.left,  lo, hi),
                 query(node.right, lo, hi))
  # ≤ 2 nodes visited per level → O(log n)

The marked lines are where the cost lives.

Range *updates* need lazy propagation — a pending marker pushed down on the way past. Without it a range update degrades to touching every leaf.

Index i stores the sum of a block whose length is the lowest set bit of i. A prefix sum therefore adds one value per set bit of i — at most log n of them — and an update walks the same bits upward. That is the whole structure: no nodes, no pointers, one array.

prefix_sum(t, i):
  s = 0
  while i > 0:
    s += t[i]
    i -= i & -i        # clear lowest set bit
  return s               # ≤ log n iterations

The marked lines are where the cost lives.

Range sums work because subtraction undoes a prefix. There is no such trick for min or max — that is what a segment tree is for.

Each level splits space on a different axis, so a nearest-neighbour search descends to a leaf and then only revisits branches whose bounding region is closer than the best match so far. In low dimensions that prunes almost everything; the cost is logarithmic on average.

nearest(node, target, best):
  best = closer_of(best, node.point)
  near, far = sides_of(node, target)
  best = nearest(near, target, best)
  if distance_to_plane(node, target) < best.dist:
    best = nearest(far, target, best)   # pruned, usually
  return best

The marked lines are where the cost lives.

Past roughly ten dimensions almost every branch survives pruning and the search degenerates to a scan of all n points. The curse of dimensionality, visible in the bound.

The array is an implicit complete tree: children of i live at 2i+1 and 2i+2. Insert appends and swims the value up at most log n levels; extract-min moves the last element to the root and sinks it down at most log n levels. Building from n items is O(n), not O(n log n), because most nodes are near the leaves and sink almost nowhere.

extract_min(h):
  min = h[0]
  h[0] = h.pop()            # move last to root
  i = 0
  while child(i) < h[i]:    # sink: ≤ log n swaps
    swap(i, smaller_child(i))
    i = smaller_child(i)
  return min

The marked lines are where the cost lives.

Finding an arbitrary element is O(n) — the heap only orders parents against children. decrease-key needs an external index from key to position.

A forest of trees whose sizes are the powers of two in n. Merging two heaps is binary addition on that forest, carrying like bits — log n work. Everything else falls out of merge.

merge(a, b):
  # like adding two binary numbers
  for each order k in 0..log n:
    combine trees of order k, carry order k+1
 
insert(h, x): merge(h, single_node_heap(x))

The marked lines are where the cost lives.

Its reason to exist is meldability. If you never merge two heaps, a binary heap does the same work with a fraction of the pointer chasing.

Insert and decrease-key do the minimum possible work — splice a node into a root list and move on — and defer the tidying to the next extract-min, which consolidates trees of equal degree. Amortised over a sequence, that is O(1) for the lazy operations and O(log n) for extract.

decrease_key(h, node, k):
  node.key = k
  if node.key < node.parent.key:
    cut(node) → root list      # O(1), no rebalancing
    cascading_cut(node.parent)
  # the tidy-up is deferred to extract_min

The marked lines are where the cost lives.

Amortised, not per-operation: one extract-min pays for all the deferred work, and the per-node bookkeeping is heavy enough that binary heaps usually win in practice.

Each set is a tree; find walks to the root. Union by rank keeps trees shallow, and path compression flattens every node it walks past straight onto the root, so the same walk never happens twice. Together they give α(n) amortised — under five for any n that fits in a computer.

find(x):
  if parent[x] != x:
    parent[x] = find(parent[x])   # compress on the way out
  return parent[x]
 
union(a, b):
  ra, rb = find(a), find(b)
  attach the shorter tree under the taller  # by rank

The marked lines are where the cost lives.

Either optimisation alone gives O(log n). People implement one, measure, and conclude the structure is slow.