Complexity Reference
Big-O notation reference for data structures, algorithms, and system design components.
Array / Dynamic Array
Contiguous memory, index-based access. ArrayList (Java), list (Python), vector (C++).
| Operation | Average | Worst | Space | Notes |
|---|---|---|---|---|
| Access by index | O(1) | O(1) | O(n) | Direct address calculation |
| Search (unsorted) | O(n) | O(n) | O(1) | Linear scan |
| Search (sorted) | O(log n) | O(log n) | O(1) | Binary search |
| Insert at end | O(1)* | O(n) | O(n) | *Amortized, worst case resizes |
| Insert at beginning | O(n) | O(n) | O(n) | Must shift all elements |
| Delete | O(n) | O(n) | O(n) | Must shift elements |
Hash Table
Key-value pairs with O(1) average access. HashMap (Java), dict (Python), object/Map (JS).
| Operation | Average | Worst | Space | Notes |
|---|---|---|---|---|
| Get | O(1) | O(n) | O(n) | O(n) with hash collisions |
| Put | O(1) | O(n) | O(n) | Amortized with resizing |
| Delete | O(1) | O(n) | O(n) | O(n) with collisions |
| Contains | O(1) | O(n) | O(n) | Hash lookup |
Balanced BST (Red-Black / AVL)
Self-balancing binary search tree. TreeMap (Java), std::map (C++). Ordered operations.
| Operation | Average | Worst | Space | Notes |
|---|---|---|---|---|
| Search | O(log n) | O(log n) | O(n) | Always balanced |
| Insert | O(log n) | O(log n) | O(n) | Rebalance after insert |
| Delete | O(log n) | O(log n) | O(n) | Rebalance after delete |
| Min / Max | O(log n) | O(log n) | O(1) | Traverse to leaf |
| Range query | O(log n + k) | O(log n + k) | O(k) | k = results count |
Heap (Priority Queue)
Complete binary tree. Min-heap or max-heap. PriorityQueue (Java), heapq (Python).
| Operation | Average | Worst | Space | Notes |
|---|---|---|---|---|
| Find min/max | O(1) | O(1) | O(n) | Always at root |
| Insert | O(log n) | O(log n) | O(n) | Bubble up |
| Extract min/max | O(log n) | O(log n) | O(n) | Bubble down |
| Build heap | O(n) | O(n) | O(n) | Bottom-up heapify |
Trie (Prefix Tree)
Tree for string storage. Each node represents a character. Used for autocomplete.
| Operation | Average | Worst | Space | Notes |
|---|---|---|---|---|
| Search word | O(m) | O(m) | O(n*m) | m = word length |
| Insert word | O(m) | O(m) | O(n*m) | m = word length |
| Prefix search | O(p + k) | O(p + k) | O(n*m) | p = prefix len, k = results |
Bloom Filter
Probabilistic set membership. Space-efficient. False positives possible, no false negatives.
| Operation | Average | Worst | Space | Notes |
|---|---|---|---|---|
| Add | O(k) | O(k) | O(m) | k = hash functions |
| Check membership | O(k) | O(k) | O(m) | May have false positives |
| Delete | N/A | N/A | - | Not supported (use counting BF) |
Big-O at a Glance
O(1)
Constant
Hash lookup
O(log n)
Logarithmic
Binary search
O(n)
Linear
Array scan
O(n log n)
Linearithmic
Merge sort
O(n²)
Quadratic
Nested loops
O(2ⁿ)
Exponential
Subsets
O(n!)
Factorial
Permutations
O(1) amort
Amortized
Dynamic array