Part App. · Appendices
A. Algorithm and Data Structure Complexity Reference
9 lessons•32 topics•Reference
0 of 9 lessons published
A.01Outline
Asymptotic shorthand
- Constant O(1)
- Logarithmic O(log n)
- Linear O(n)
- Linearithmic O(n log n)
- Quadratic O(n²)
- Exponential O(2^n)
A.02Outline
Array complexity
- Index O(1)
- Linear find O(n)
- Middle insertion/deletion O(n)
- Append dynamic amortized O(1)
A.03Outline
Linked list complexity
- Known-node insertion O(1)
- Search O(n)
- Index access O(n)
- Head insertion/removal O(1)
A.04Outline
Hash table complexity
- Expected lookup/insert/delete O(1)
- Potential worst-case O(n)
- Depends on hashing and implementation
A.05Outline
Balanced BST complexity
- Search/insert/delete O(log n)
- Sorted traversal O(n)
- Range query O(log n+k) typical
A.06Outline
Heap complexity
- Peek O(1)
- Push/pop O(log n)
- Heapify O(n)
- Search arbitrary element O(n)
A.07Outline
Common sorts
- Bubble/selection/insertion worst O(n²)
- Merge/heap O(n log n)
- Quicksort expected O(n log n), worst O(n²)
A.08Outline
Graph traversal complexity
- BFS/DFS O(V+E) adjacency list
- Dense adjacency matrix may incur O(V²)
A.09Outline
Range structures
- Fenwick update/query O(log n)
- Segment tree update/query O(log n)
- Sparse table RMQ query O(1)