Cheat sheet + 20 flashcards covering Big-O complexity, core data structures, sorting, graphs, and dynamic programming.
Best → Worst: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
Access by index: O(1)
Search (unsorted): O(n)
Search (sorted, binary): O(log n)
Insert/Delete (end): O(1) amortised
Insert/Delete (middle): O(n) — must shift elements
Space: O(n)
Access: O(n) — no random access
Insert/Delete at head: O(1)
Insert/Delete at tail: O(1) with tail pointer
Search: O(n)
Doubly adds prev pointer — enables backward traversal & O(1) delete given node
Stack (LIFO) — push, pop, peek: all O(1). Uses: undo history, call stack, DFS, bracket matching.
Queue (FIFO) — enqueue, dequeue, front: all O(1). Uses: BFS, task scheduling, print queue.
BST search/insert: O(log n) avg, O(n) worst (skewed)
Height of balanced tree: O(log n)
In-order: L → Root → R (BST → sorted)
Pre-order: Root → L → R (copy tree)
Post-order: L → R → Root (delete tree)
Get / Set / Delete: O(1) avg, O(n) worst (all collide)
Space: O(n)
Collision resolution:
Chaining — bucket holds a linked list
Open addressing — probe for next empty slot (linear, quadratic, double hash)
Adjacency List — O(V+E) space. Best for sparse graphs. Faster to iterate neighbours.
Adjacency Matrix — O(V²) space. O(1) edge lookup. Best for dense graphs.
BFS: O(V+E) · DFS: O(V+E)
Complete binary tree stored as array.
Max-heap: parent ≥ children · Min-heap: parent ≤ children
Insert (heapify up): O(log n)
Extract max/min: O(log n)
Peek max/min: O(1)
Build heap from array: O(n)
Bubble / Selection / Insertion: O(n²) — simple, in-place
Merge Sort: O(n log n) — stable, extra O(n) space
Quick Sort: O(n log n) avg / O(n²) worst — in-place
Heap Sort: O(n log n) — in-place, not stable
Counting / Radix: O(n+k) — non-comparison
Break problem into overlapping subproblems, cache results.
Memoization (top-down): recursion + cache. Natural to write.
Tabulation (bottom-up): fill table iteratively. No stack overflow risk.
Classic problems: Fibonacci, Knapsack, Longest Common Subsequence, Coin Change.
Space flip · → next · ← prev · G got it · R review