DATA STRUCTURES · COMPLEXITY · TRADE-OFFS
Big O is
not a speed.
It describes how cost grows as input grows. The fastest structure is therefore not a universal winner: it is the one whose cheap operations match your hot path, whose guarantees match your risk, and whose memory layout fits the machine.
same Big O ≠ same runtime
01 / READ THE NOTATION
One letter hides
three different promises.
Complexity claims are only useful when you know which case they describe and what the input variable represents.
O( )
An upper bound. The operation will not grow faster than this class beyond some input size. It is the safety-oriented view.
Θ( )
The actual growth class is bounded above and below. Saying array indexing is Θ(1) is more precise than merely O(1).
Σ / m
An expensive operation is spread across a sequence. Dynamic-array append is usually constant on average over many appends, although one resize is O(n).
Average case assumes a distribution of inputs. Hash-table lookup is average Θ(1), but collisions can produce O(n) worst-case behavior. That distinction matters for untrusted keys and latency-sensitive systems.
Also name the variable. A trie lookup is O(L), where L is key length. Graph traversal is O(V + E), not simply O(n). Good analysis defines the unit before comparing curves.
THE FIRST RULEDrop constants in the model. Measure them in the system.
02 / THE COMPARISON TABLE
Complexity is a
cost profile.
These are common implementation guarantees. Language runtimes can differ, so treat the table as a map and verify the concrete container you use.
| STRUCTURE | ACCESS / PEEK | SEARCH | INSERT | DELETE | BEST FIT |
|---|---|---|---|---|---|
| Dynamic array | Θ(1) | O(n) | Amortized Θ(1) | O(n) | |
| Linked list | O(n) | O(n) | Θ(1)* | Θ(1)* | |
| Hash table | — | Average Θ(1) | Average Θ(1) | Average Θ(1) | |
| Balanced BST | Min/max O(log n) | O(log n) | O(log n) | O(log n) | |
| Binary heap | Peek Θ(1) | O(n) | O(log n) | Root O(log n) | |
| Stack / queue | Peek Θ(1) | — | Θ(1) | Θ(1) | |
| Trie | — | O(L) | O(L) | O(L) | |
Linked-list insert and delete are Θ(1) only when you already have the relevant node (and, for deletion, the required predecessor or a doubly linked list). Finding that node is O(n). This footnote changes many interview answers—and many production designs.
03 / WHERE EACH ONE WINS
No champion.
Only a better fit.
A structure wins when it makes the dominant operation cheap without charging unacceptable costs elsewhere.
Dynamic array
- USE WHEN
- Indexed reads, compact storage, and full scans.
- WINS
- Better locality than linked nodes; often faster in practice even when both operations are O(n).
- PAYS WITH
- Middle insertion shifts elements; growth occasionally copies the backing storage.
Hash table
- USE WHEN
- Membership, deduplication, counters, caches, and exact-key joins.
- WINS
- Average O(1) lookup beats a tree or array when ordering is irrelevant.
- PAYS WITH
- No sorted traversal; collisions, resizing, and hash quality affect latency and memory.
Balanced tree
- USE WHEN
- Sorted iteration, predecessor/successor, and range queries.
- WINS
- O(log n) operations with useful order—something a hash table cannot provide.
- PAYS WITH
- More pointer chasing and slower exact lookup constants than a good hash table.
Binary heap
- USE WHEN
- Schedulers, top-k queries, and priority queues.
- WINS
- O(1) peek and O(log n) push/pop without paying to keep every element fully sorted.
- PAYS WITH
- Finding an arbitrary item is O(n); it is not a general-purpose search structure.
Stack / queue
- USE WHEN
- Undo, parsing, BFS, work buffers, and streaming pipelines.
- WINS
- O(1) operations encode the required order directly and keep the API constrained.
- PAYS WITH
- They intentionally do not optimize arbitrary access or search.
Trie
- USE WHEN
- Autocomplete, routing tables, and prefix dictionaries.
- WINS
- O(L) depends on key length, not the number of stored keys.
- PAYS WITH
- High memory overhead; a sorted array can be smaller and cache-friendlier.
04 / START FROM THE QUERY
Turn requirements
into operations.
“Store some items” is not a workload. The question you ask repeatedly is what should shape the structure.
- 01
Need item #i
Dynamic array. Direct addressing gives Θ(1) access and contiguous memory.
- 02
Need exact key x
Hash table. Average Θ(1) membership; use a set when values are unnecessary.
- 03
Need keys between a and b
Balanced tree. Ordering makes range traversal O(log n + k) for k results.
- 04
Need the next highest priority
Binary heap. Peek in O(1), then remove in O(log n).
- 05
Need all keys beginning with pre
Trie. Walk the prefix in O(L), then enumerate its subtree.
- 06
Need FIFO or LIFO only
Queue or stack. The restricted interface makes both end operations O(1).
- 07
Need to scan everything
Dynamic array. Contiguous layout usually wins on cache locality and overhead.
An LRU cache commonly uses a hash table for O(1) key lookup plus a doubly linked list for O(1) recency updates. A database index may use a B-tree while its buffer manager uses a hash table and queues. Choose per operation, not once per application.
05 / BIG O MEETS HARDWARE
Asymptotics predict.
Machines decide.
For finite data, representation and access pattern can outweigh the headline complexity.
Cache locality
Arrays place neighboring values together. CPUs fetch cache lines, so sequential scans can beat pointer-heavy structures by a wide margin.
An O(n) array scan may outperform theoretically better lookup at small or moderate n.
Memory overhead
Pointers, empty hash buckets, tree nodes, and trie edges consume memory beyond the stored values.
A compact sorted array can be the better read-mostly index despite O(log n) lookup.
Input distribution
Hash collisions, skewed trees, hot keys, and repeated prefixes change observed behavior.
Benchmark representative data, including adversarial or pathological cases when relevant.
Mutation rate
A structure optimized for reads may pay heavily to preserve order or rebuild storage on writes.
Include the read/write ratio, batching, concurrency, and allocation cost in the decision.
06 / A PRACTICAL METHOD
Choose, measure,
then defend.
The simplest structure that meets the actual access pattern is usually the best starting point.
- 01
List the operations
Write down reads, writes, deletes, scans, ranges, prefix queries, and min/max extraction.
- 02
Weight the hot path
A million lookups and ten insertions should not influence the choice equally.
- 03
Require the right guarantee
Separate average, amortized, and worst case; decide which latency tail can hurt the product.
- 04
Estimate scale and memory
Use realistic n, key length, object size, growth, and concurrency—not an abstract infinite input.
- 05
Prefer the standard library
Its containers are tested and optimized. Introduce a custom structure only with evidence.
- 06
Benchmark the workload
Measure latency distribution, memory, allocations, and throughput with production-shaped data.
DESIGN REVIEW
Before choosing
the container.
- 01What operations dominate: lookup, traversal, insertion, deletion, range, or min/max?
- 02Do I need ordering, stable iteration, prefixes, or only exact keys?
- 03Am I comparing average, amortized, or worst-case guarantees?
- 04What are n and L in this workload, and how large will they become?
- 05Does memory layout or allocation overhead matter more than asymptotic growth?
- 06Can the standard library structure express this workload safely?
- 07Did I benchmark with production-like size, distribution, and access patterns?
THE DECISION IN ONE LINE
Optimize the operation,
not the name.
Big O narrows the search. Workload shape, guarantees, memory behavior, and measurement finish the decision. Start with what the system does most, then make that path deliberately cheap.
07 / SOURCES & NEXT STEPS