Data Structures and Algorithm Analysis
This domain tests abstract data types, operation costs, and Big-O reasoning. You should be able to choose a structure for a task and justify the choice with average and worst-case complexity.
Core structures
- Arrays support O(1) indexed access but O(n) insertion or deletion in the middle.
- Linked lists support O(1) insertion at a known node but O(n) search and no direct indexing.
- Stacks are LIFO; queues are FIFO. Both support O(1) push/enqueue and pop/dequeue when implemented well.
- Binary search trees average O(log n) search when balanced but degrade to O(n) in a skewed tree.
- Hash tables average O(1) lookup, though collisions and poor hash functions worsen performance.
- Graphs use adjacency matrices for dense graphs and adjacency lists for sparse graphs.
Analysis rules
Big-O describes an upper bound on growth. Count the dominant operation, drop constants, and keep the fastest-growing term. Sequential blocks add costs; nested loops multiply them. Binary search is O(log n) but requires sorted data.
Worked example
How many comparisons does binary search need in the worst case for 1,024 sorted elements? Each comparison halves the remaining range, so after k comparisons about 1,024 / 2^k elements remain. Set 1,024 / 2^k = 1, giving 2^k = 1,024 and k = 10. The worst case is therefore about 10 comparisons, matching O(log n). A linear search could need 1,024 comparisons.
Traps that cost marks
- Saying a linked list has O(1) random access.
- Quoting average-case hash-table time as a worst-case guarantee.
- Forgetting that binary search requires sorted input.
- Assuming every BST operation is O(log n) even when the tree is skewed.
- Dropping the wrong term when adding complexities such as O(n) + O(n log n).