Data Structures and Algorithms
Data Structures and Algorithms tests selection and analysis: choosing an appropriate structure, stating complexity correctly, and tracing an algorithm on a small input. Expect trees, hashing, sorting, graph traversal, and recursion.
Core rules
Arrays give O(1) indexed access but O(n) insertion in the middle; linked lists reverse that trade-off. Stacks are LIFO and queues are FIFO. Balanced search trees support O(log n) search, insert, and delete; an unbalanced binary search tree can degrade to O(n). Hash tables give average O(1) lookup but O(n) worst case with collisions. Comparison sorting has an Ω(n log n) lower bound in the general case, while counting sort can be O(n+k) for bounded integer keys. BFS finds shortest paths in unweighted graphs; DFS is for reachability and structure.
Worked example
Binary search on a sorted array of 1,024 elements. Each comparison halves the remaining range: 1,024 → 512 → 256 → … → 1. The worst-case comparison count is floor(log2 1024) + 1 = 10 + 1 = 11. Stating O(log n) is correct asymptotically, but the exam may ask for the exact count.
Traps
Big-O hides constants and lower-order terms, so it does not decide between two O(n log n) sorts by itself. Hash tables are not guaranteed O(1). Quicksort's average case is O(n log n), but its worst case is O(n^2), for example with poor pivots on sorted input. A heap is not fully sorted; only the root is guaranteed to be the extreme value.