Complexity Cheat Sheet
Quick reference for time and space complexity of every pattern's key operations. Use this to compare trade-offs before choosing a pattern.
How to Read This
- n = number of elements / items
- k = key length (for string-keyed structures)
- m = number of hash functions (Bloom filter)
- L = number of levels (skip list, LSM tree)
- Amortized costs marked with (amort.)
Data Structures
| Pattern | Insert | Lookup | Delete | Space | Notes |
|---|---|---|---|---|---|
| Bitmask | O(1) | O(1) | O(1) | O(1) | Fixed-size; limited to word width (32/64 flags) |
| Ring Buffer | O(1) | O(1) | O(1) | O(n) | Fixed capacity; overwrites oldest on full |
| Tagged Union | — | O(1) | — | O(max variant) | Dispatch by tag; no dynamic allocation |
| Min Heap | O(log n) | O(1) peek | O(log n) | O(n) | O(1) min access; used for priority queues |
| Trie | O(k) | O(k) | O(k) | O(n × k) | Independent of total entries; prefix queries O(k + results) |
| Bloom Filter | O(m) | O(m) | ✗ | O(n) | Probabilistic; false positives possible, no false negatives |
| LRU Cache | O(1) | O(1) | O(1) | O(n) | Hash map + doubly linked list |
| Skip List | O(log n) avg | O(log n) avg | O(log n) avg | O(n) | Probabilistic balancing; range queries supported |
| B+ Tree | O(log n) | O(log n) | O(log n) | O(n) | Disk-optimized; high fan-out minimizes I/O |
| Merkle Tree | O(log n) | O(log n) | O(log n) | O(n) | Verification O(log n) proofs |
| Merge Iterator | — | O(log k) next | — | O(k) | k = number of streams; heap-based merge |
Concurrency
| Pattern | Key Operation | Cost | Space | Notes |
|---|---|---|---|---|
| Semaphore | acquire / release | O(1) | O(1) | Counter-based; may block on contention |
| Double Buffering | swap | O(1) | O(2n) | Pointer swap; no copy |
| Event Loop | enqueue / dequeue | O(1) | O(queue) | Single-threaded; I/O multiplexed |
| Backpressure | signal / check | O(1) | O(1) | Flow control; often piggybacked on existing channel |
| Copy-on-Write | read | O(1) | O(n) per snapshot | Write triggers O(n) clone; reads never block |
| Cooperative Scheduling | yield | O(1) | O(tasks) | Requires voluntary yield points |
| MVCC | read / write | O(1) + GC | O(n × versions) | Reads never block; GC cost amortized |
| Work Stealing | push / steal | O(1) amort. | O(tasks) | Lock-free deque; cache-line aware |
| Actor Model | send message | O(1) | O(actors × mailbox) | Isolated state; no shared memory |
| Logical Clock | tick / merge | O(1) Lamport, O(n) Vector | O(1) / O(n) | Vector clock grows with node count |
System
| Pattern | Key Operation | Cost | Space | Notes |
|---|---|---|---|---|
| State Machine | transition | O(1) | O(states) | Constant-time dispatch; explicit states |
| Circuit Breaker | call / check | O(1) | O(1) | Counter + timer; 3 states |
| Rate Limiter | allow? | O(1) | O(1) per limiter | Token bucket or sliding window |
| Retry with Backoff | retry | O(retries) total | O(1) | Exponential delay + jitter |
| Batch Processing | flush | O(batch) | O(batch) | Amortizes per-item overhead |
| Middleware Chain | execute | O(middlewares) | O(middlewares) | Linear pipeline; each handler O(1) |
| Registry | register / lookup | O(1) hash | O(n) | String-keyed service locator |
| Dirty Flag | check / mark | O(1) | O(1) | Boolean guard; skip unchanged |
| Dependency Graph | topo sort | O(V + E) | O(V + E) | DAG; detects cycles |
| Consistent Hashing | lookup node | O(log n) | O(n × vnodes) | Binary search on ring; minimal reshuffling |
| Write-Ahead Log | append | O(1) amort. | O(log size) | Sequential writes; fsync for durability |
| Checkpointing | snapshot | O(state size) | O(state size) | Periodic; truncates WAL |
| LSM Tree | write / read | O(1) write, O(L) read | O(n) | Write-optimized; compaction in background |
Memory
| Pattern | Allocate | Free | Lookup | Space | Notes |
|---|---|---|---|---|---|
| Object Pool | O(1) | O(1) | — | O(pool size) | Pre-allocated; avoids GC pressure |
| Flyweight | — | — | O(1) | O(unique) | Share identical instances |
| Arena Allocator | O(1) bump | O(1) bulk | — | O(arena size) | Bump pointer; free all at once |
| Free List | O(1) | O(1) | — | O(n) | Linked list of freed slots |
| Copy-on-Write | O(1) share | O(n) on write | O(1) | O(n) per snapshot | Deferred copy |
| Reference Counting | O(1) clone | O(1) drop | — | O(1) per ref | Deterministic; no cycles |
| Tombstone | — | O(1) mark | O(1) | O(n + deleted) | Soft delete; compacted later |
| Interning | O(k) first, O(1) after | — | O(1) | O(unique × k) | Hash-based dedup; compare by pointer |
Behavioral
| Pattern | Key Operation | Cost | Space | Notes |
|---|---|---|---|---|
| Observer | notify | O(subscribers) | O(subscribers) | Fan-out; order may vary |
| Iterator | next | O(1) per step | O(1) | Lazy evaluation; pull-based |
| Diff / Patch | diff | O(n × m) Myers | O(n + m) | Minimal edit distance |
| Vtable | dispatch | O(1) | O(methods) | Pointer indirection; static resolution |
| Visitor | visit | O(nodes) | O(tree depth) | Double dispatch; traversal + operation |
Key Trade-offs Summary
| If you need... | Choose | Trade-off |
|---|---|---|
| O(1) lookup + O(1) eviction | LRU Cache | Extra memory for doubly linked list |
| O(1) writes at scale | LSM Tree | Read amplification (multiple levels) |
| O(1) membership test | Bloom Filter | False positives (no false negatives) |
| O(1) allocation | Arena or Free List | No individual free (arena) or fragmentation (free list) |
| O(log n) sorted access | Skip List or B+ Tree | Skip list simpler, B+ tree disk-optimized |
| Zero-copy reads | Copy-on-Write or MVCC | Write amplification on mutation |
| Minimal rehash on scale | Consistent Hashing | Virtual nodes add memory overhead |