Programming Fundamentals and Data Structures
Domain 4 tests complexity analysis and the selection of the right data structure for an operation mix. Questions are usually small code snippets, complexity ranking, or a design scenario needing a stated asymptotic bound.
Complexity and core structures
Big-O gives an upper bound on growth; drop constants and lower-order terms. Array index access O(1). Linked list insert or delete at a known node O(1), search O(n). Hash table average O(1) lookup, worst case O(n) under collisions or adversarial keys. Balanced BST O(log n) search and insert, in-order traversal O(n) and sorted. Binary heap insert and extract-min O(log n), peek O(1), heap construction O(n). Graph BFS and DFS O(V+E). Amortized analysis explains why dynamic array append is O(1) amortized despite occasional O(n) resizing.
Sorting and searching
Merge sort O(n log n) in all cases, stable, O(n) extra space. Quicksort average O(n log n), worst case O(n squared) on adversarial or poorly pivoted input, in-place, unstable. Heapsort O(n log n) worst case, in-place, unstable. Binary search is O(log n) and requires sorted data; write mid = lo + (hi - lo)/2 to avoid overflow and keep the loop invariant consistent with the bounds update.
Worked example
Design a fixed-capacity LRU cache with O(1) get and put. Reasoning: O(1) key lookup demands a hash map from key to node. O(1) eviction of the least recently used entry plus O(1) promotion of a hit demands a doubly linked list, because a singly linked list would need O(n) to unlink a node given only that node. Combine them: get moves the node to the head; put inserts at the head, and when at capacity removes the tail and deletes its key from the map. A sorted array would cost O(n) to reorder on each access, violating the bound.
Traps that cost marks
- Stating hash lookup is always O(1); the worst case is O(n).
- Applying binary search to unsorted data.
- Off-by-one errors when mixing while (lo <= hi) with hi = mid - 1.
- Recursion without a base case, or ignoring stack depth.
- Claiming quicksort is always O(n log n) or that merge sort is in-place.
- Ignoring stability when records are sorted by multiple keys.