Data Structure Complexity

The full time/space table for every structure you reach for — average and worst case, at a glance. The interview reference.

Big-O describes how an operation’s cost grows with the number of elements n, ignoring constant factors. The table gives average and worst case where they differ, because that gap is often the whole point: a hash table is O(1) on average but O(n) when keys collide, and a plain BST degrades into a linked list on sorted input.

Amortized means averaged over a long sequence of operations, so an occasional expensive step, such as a dynamic array resize, is spread across many cheap ones. Choose a structure by its most frequent operation, then check the worst case if latency matters.

Linear structures (avg / worst)

Array (static): access O(1) · search O(n) · insert/delete O(n) · space O(n)
Dynamic array: access O(1) · append O(1) amortized · insert/delete O(n)
Sorted array: binary search O(log n) · insert/delete O(n) — great for read-mostly data
Singly linked list: access/search O(n) · insert/delete at head O(1)
Doubly linked list: same, plus O(1) delete given the node
Stack / Queue: push/pop/enqueue/dequeue O(1)
Ring buffer: fixed capacity; both ends and indexing O(1) — logs, sliding windows

Hash & trees

Hash table: search/insert/delete O(1) avg · O(n) worst (bad hashing)
Hash set: membership O(1) average; iteration order is not something to rely on
Binary search tree: O(log n) avg · O(n) worst (degenerate/unbalanced)
Balanced BST (AVL / RB): search/insert/delete O(log n) worst — guaranteed
Splay tree · treap: O(log n) amortized (splay) or expected (treap); splaying moves hot keys up
B-tree: O(log n) · high fan-out → few disk reads (DB indexes)
B+ tree: values only in linked leaves: O(log n) lookups plus fast range scans
LSM tree: buffered writes flushed sequentially — cheap inserts; reads may check several levels
Trie: search/insert O(L) in key length L (not n)

Heaps & priority queues

Binary heap: peek O(1) · push/pop O(log n) · build O(n)
Decrease-key: binary heap O(log n) with an index map; Fibonacci heap O(1) amortized
Top-k of a stream: min-heap of size k: O(n log k) time, O(k) space
Running median: two heaps (max below, min above): O(log n) insert, O(1) median

Graphs & strings

Adjacency list: space O(V + E) · edge check O(degree) — the default for sparse graphs
Adjacency matrix: space O(V²) · edge check O(1) — only for dense or small graphs
BFS / DFS: O(V + E) on an adjacency list
Dijkstra (binary heap): O((V + E) log V); non-negative edge weights only
String concat in a loop: O(n²) with immutable strings — collect parts and join once
Substring search: naive O(n·m); KMP guarantees O(n + m)
Suffix array: build O(n log n) · find a pattern of length m in O(m log n)

Probabilistic & specialized

Skip list: search/insert/delete O(log n) expected · space O(n)
Bloom filter: add/query O(k) hashes · space sublinear · false positives, no false negatives
Count-min sketch: frequency estimates in fixed memory; O(k) per update, never underestimates
HyperLogLog: count distinct with ~1.04/√m error — Redis uses 12 KB for ~0.81%
Fenwick / segment tree: point update + range query O(log n)
Sparse table: static range-min in O(1) after an O(n log n) build; no updates
Interval tree: augmented BST: one overlap in O(log n), all k in O(min(n, k log n))
Union-Find: near O(1) amortized (inverse-Ackermann) with path compression + rank
LRU cache: get/put O(1) — hash map + doubly linked list

Language built-ins

Python list: append and pop() O(1); pop(0), insert(0, x) and x in list are O(n)
Python dict / set: get, set, delete and in are O(1) average; dicts keep insertion order
Java HashMap: O(1) average; crowded buckets become trees, so O(log n) worst for Comparable keys
C++ map · unordered_map: red-black tree O(log n), ordered · hash table O(1) average
JS array shift(): can be O(n); a head index over an array makes a true O(1) queue

Rules of thumb

Need ordering?: Balanced BST / skip list — O(log n) with sorted traversal.
Only membership/lookup?: Hash table — O(1), no order.
Need min/max repeatedly?: Heap — O(log n) push/pop.
Latency SLA?: When the worst case matters, avoid plain hash/BST; use balanced trees or bounded structures.
Need prefix search?: Trie — O(L) per lookup; a sorted array works for static sets
Sliding-window max?: monotonic deque — O(n) total, O(1) amortized per step

Gotchas

Amortized ≠ worst case: a dynamic array append is O(1) amortized but O(n) on the resize
Growth factor: amortized O(1) needs geometric growth (×1.5–2), not a fixed increment
Cache locality: arrays beat linked lists at equal big-O because contiguous memory suits the CPU cache
Hash flooding: crafted colliding keys force O(n) lookups; randomized hashing defends against it

Recipes

Choose a structure for a leaderboard

Operations:  update a score (often), top 10 (often), a user's rank (sometimes)
Hash map:    update O(1), but top 10 means sorting on every query       ✗
Heap:        top 10 is cheap, but a user's rank is O(n)                 ✗
Skip list or balanced tree keyed by (score, user), with subtree counts:
             update O(log n), top 10 O(log n + 10), rank O(log n)       ✓
Plus a hash map user → score, so an update finds the old entry in O(1)

This combination is exactly a Redis sorted set: a skip list for order and ranks, plus a hash table for lookups by member.

Why building a heap is O(n)

Height from the bottom:   0      1      2      ...   h
Nodes at that height:     n/2    n/4    n/8    ...   1
Sift-down cost per node:  0      1      2      ...   h
Total work:  sum over k of (n / 2^(k+1)) × k  =  n × (1/4 + 2/8 + 3/16 + ...)  ≤  n

Most nodes sit near the bottom, where sifting down is cheap, so bottom-up heapify is linear even though n separate pushes would cost O(n log n).

Top-k from a stream of a billion items

Full sort:        O(n log n) time, O(n) memory     → all 1B items in memory    ✗
Min-heap of k:    O(n log k) time, O(k) memory     → k = 100, log k ≈ 7        ✓
Quickselect:      O(n) average, but needs every item in memory                 ✗
Heavy hitters:    a count-min sketch plus a small heap, in fixed memory

Keep the k largest seen so far in a min-heap; a new item replaces the root only when it beats the smallest of them.

Linked list, array or ring buffer for a queue?

Array with pop(0):    O(n) per dequeue → n dequeues cost O(n²)
Linked list:          O(1) per operation, but a pointer per node and poor locality
Ring buffer / deque:  O(1) per operation in contiguous memory → usually fastest

Equal big-O is not equal speed: at the same O(1), a contiguous ring buffer beats a linked list because the CPU cache does the rest.

Questions about Data Structure Complexity Cheat Sheet

What is the time complexity of a hash table?

Insert, lookup and delete take O(1) time on average, because a good hash function spreads keys evenly and the table resizes to keep buckets short. The worst case is O(n), when many keys land in the same bucket through a poor hash function or deliberately crafted keys, which is why many languages randomize their hashing. Resizing costs O(n) occasionally, but amortized over all insertions it stays O(1) each. Java’s HashMap turns long buckets into balanced trees, which limits the worst case to O(log n) for comparable keys.

What does amortized time complexity mean?

Amortized complexity is the average cost per operation over a worst-case sequence of operations, rather than the cost of any single one. The classic example is appending to a dynamic array: most appends write into spare capacity in O(1), but when the array is full it allocates a larger block and copies everything in O(n). Because capacity grows geometrically, typically by 1.5 to 2 times, the copies are rare enough that n appends cost O(n) in total, or O(1) amortized each, even though one append can be slow.

When should I use a linked list instead of an array?

Rarely, in modern code. Linked lists win when you need O(1) insertion or removal in the middle of a sequence at a position you already hold a reference to, as in an LRU cache’s recency list, or when elements must never move in memory. For most other uses dynamic arrays are faster even when the big-O is equal or slightly worse, because their contiguous layout suits the CPU cache, while every list node is a separate allocation and a pointer chase. Default to arrays and deques, and measure before switching.

Go deeper

Big-O cheatsheet →Algorithms — played in 3D →