Algorithms and Problem Solving: Searching, Sorting, and Simple Complexity Reasoning
Algorithms and problem solving covers searching, sorting, and the running-time reasoning that lets you choose between them. The exam asks you to trace an algorithm on a small input, recognise its complexity, and justify a data-structure choice.
Searching
Linear search checks each element in turn: O(n) time, works on unsorted data. Binary search repeatedly halves a sorted range: O(log n) time, but correct only on sorted input. In Python, in on a list is linear; on a set or dict it is average O(1).
Sorting
Elementary sorts - bubble, insertion, selection - are O(n²) and mainly useful for understanding. Merge sort and efficient library sorts are O(n log n). sorted() and list.sort() are stable in Python, so equal elements keep their original order, which enables tricks such as sorting by a secondary key first.
Complexity reasoning
Count how many times the inner operation runs as a function of n. One loop over n items is O(n); a loop containing another loop is O(n²); halving the range each step is O(log n); sorting then scanning is O(n log n). Big-O describes growth, not exact speed, and constants matter for small inputs.
Worked example
Search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91].
- low=0, high=9, mid=4 gives value 16; 23 > 16, so low=5.
- low=5, high=9, mid=7 gives value 56; 23 < 56, so high=6.
- low=5, high=6, mid=5 gives value 23; found. Three comparisons instead of ten for linear search. The array was sorted, which is the precondition for binary search.
Traps
- Running binary search on an unsorted array.
- Off-by-one in the
low <= highcondition or in the midpoint calculation. - Calling an O(n²) sort inside a loop, making the whole program O(n³).
- Assuming dict iteration is sorted.
- Forgetting that
sort()mutates in place whilesorted()returns a new list.