Big-O Cheat Sheet

Access by index is O(1). Insertion and deletion are O(n) because they are measured at an arbitrary position and shift the trailing elements; appending to the end of a dynamic array is amortized O(1).

Search is O(1) only if you already know the index. Scanning for a value in an unsorted array is O(n); binary search over a sorted array is O(log n) — see the tree rows for structures that keep data ordered for you.

Push and pop act only on the top, so insertion and deletion are O(1). Reaching an element beneath the top (access or search) means popping through the ones above it, which is O(n).

Enqueue and dequeue touch only the two ends, so both are O(1); reaching an interior element is O(n). The complexity profile matches a stack — only the access order (FIFO vs LIFO) differs.

The O(1) insertion and deletion assume you already hold the node (or the head/tail). Locating that node first is a linear walk, so an insert-after-value operation is O(n) in total. There is no random access — reaching index i is O(n).

Like a singly-linked list, splicing is O(1) once you hold the node. The extra backward pointer lets you delete a known node without first scanning for its predecessor, which a singly-linked list needs; finding the node in the first place is still O(n).

The O(log n) figures are expected values over the random level assignment, not a guarantee — an unlucky build degrades to the O(n) worst case, so these cells are probabilistic rather than deterministic. Space is O(n log n) because higher express lanes duplicate node pointers.

Search, insertion and deletion are O(1) on average and amortized, but the worst case is O(n) when many keys collide into one bucket or a resize rehashes every entry.

Access has no meaning: a hash table has no positional index, so that cell is shown as an em-dash rather than a fabricated O — you look items up by key, not by position.

O(log n) assumes the tree stays roughly balanced. A plain BST fed already-sorted keys degenerates into a linked list, so its worst case is O(n). The self-balancing rows below (AVL, red-black, B-tree) buy back the O(log n) guarantee.

A binary tree derived from a sequence; access by index is not applicable, so that cell is an em-dash. Search, insertion and deletion average O(log n) but degrade to O(n) without balancing (a randomized treap keeps them expected O(log n)).

A self-balancing multi-way tree with a deterministic O(log n) worst case for every operation. Its wide, shallow shape minimizes disk seeks, which is why databases and filesystems use B-trees and their B+ variant for on-disk indexes.

A self-balancing BST with a deterministic O(log n) worst case. It rebalances with fewer rotations than an AVL tree, trading slightly looser height for cheaper writes; it backs many standard-library ordered maps and sets.

The O(log n) figures are amortized, not per-operation worst case: a single splay can cost O(n), but any sequence of m operations totals O(m log n). Splaying moves recently used keys near the root, so repeated access to a hot set is very fast.

The most rigidly balanced tree here, with a deterministic O(log n) worst case. Its tighter height makes lookups a touch faster than a red-black tree, at the cost of more rotations on insert and delete.

A binary tree that partitions k-dimensional points for range and nearest-neighbour queries. O(log n) is the balanced average; an unbalanced build degrades to O(n), and the advantage erodes as the number of dimensions grows.

The O(n²) worst case comes from consistently bad pivots — for example already-sorted input with a naive first-element pivot. Randomized or median-of-three pivots make it very unlikely in practice.

Space O(log n) is the recursion stack for the in-place partition (auxiliary space excludes the input array). Without tail-call elimination, an unbalanced recursion can push that to O(n).

Deterministic O(n log n) in every case, and stable. The O(n) space is the auxiliary buffer the merge step needs — array merge sort is not in-place. Space here is auxiliary, excluding the input; this convention holds for every row.

A hybrid of merge sort and insertion sort that detects existing sorted runs and galloping patterns, giving an O(n) best case on nearly-sorted input. It is the default sort in Python's list.sort and Java's Arrays.sort for objects, and it is stable.

Deterministic O(n log n) and in-place, so its auxiliary space is O(1). The trade-offs are that it is not stable and its scattered heap accesses have poorer cache locality than quicksort's sequential partitioning.

The O(n) best case needs the early-exit optimization: stop after a full pass that makes no swaps, which happens on already-sorted input. Without that check, best is also O(n²). Mainly of teaching interest.

O(n) best case on already-sorted input, and stable and in-place. It is genuinely fast for small or nearly-sorted arrays, which is why optimized quicksort and merge sort fall back to it below a size threshold.

There is no early exit: every pass scans the whole unsorted remainder to find the minimum, so best, average and worst are all O(n²) regardless of the input order. It does, however, make the fewest writes of the quadratic sorts.

Insert every element into a binary search tree, then read it back in order. It is O(n log n) when the tree stays balanced and O(n²) when it degenerates — the same hazard as an unbalanced BST; a self-balancing tree removes the quadratic case.

Insertion sort applied over diminishing gaps so elements move a long way early. The bounds shown assume a common gap sequence; the exact average and worst complexity of Shellsort depends on the gap sequence chosen and is still an open problem for some sequences.

A distribution sort: scatter n items into k buckets, sort each, then concatenate. It is O(n + k) when inputs spread evenly across buckets, but skewed data that piles into one bucket collapses toward the O(n²) worst case.

A non-comparison sort that processes keys digit by digit, where k is the key length (number of digits or bytes). It beats O(n log n) only when k is small relative to n; for long or unbounded keys the k factor dominates.

A non-comparison sort that tallies occurrences over a value range of size k, so it runs in O(n + k). The O(k) space makes it impractical when the range is large or sparse; it shines on small integer keys and often serves as the stable inner pass of radix sort.

A parallel sort that inserts elements into a self-balancing multidimensional array (a cube) and reads them back in order. It reaches an O(n) best case on already-ordered input and O(n log n) otherwise, and it is stable.