Data Structures and Algorithms
Data Structures and Algorithms tests selection and analysis: choosing a structure for an operation mix, proving complexity, and recognizing when a greedy choice fails.
Core rules
- Asymptotic notation ignores constants: O, Θ, Ω describe upper, tight, and lower bounds.
- Array access is O(1); insertion/deletion is O(n). Linked lists trade random access for O(1) splice once located.
- Balanced BSTs (AVL, red-black) give O(log n) search/insert/delete; hash tables give O(1) average but O(n) worst case and need collision handling.
- BFS and DFS are O(V+E). Dijkstra with a binary heap is O((V+E) log V) and fails on negative edges; Bellman–Ford handles them in O(VE).
- Comparison sorting lower bound is Ω(n log n); counting/radix sort escape it with key restrictions.
- Dynamic programming requires optimal substructure and overlapping subproblems; greedy requires a proof of local-choice safety.
Worked example
Merge sort recurrence T(n)=2T(n/2)+O(n). By the master theorem, a=2, b=2, f(n)=Θ(n), so T(n)=Θ(n log n). For n=1,048,576, log2 n=20, so the leading work is about 20n comparisons-far below n².
Hash example: insert 10,000 keys into a table with 10,000 slots and chaining. Load factor α=1; average successful search is about 1+α/2=1.5 probes under uniform hashing. If all keys collide, search degrades to O(n), showing why hash quality and resizing matter.
Traps
- Calling hash lookup O(1) worst case.
- Using Dijkstra with negative weights.
- Confusing BFS shortest path on unweighted graphs with weighted shortest path.
- Assuming a greedy algorithm is optimal without an exchange argument.