Programming and Algorithms: Tracing, Recursion and Complexity
This domain tests reading code rather than writing it: you must trace pseudocode exactly, identify the output, and classify cost with asymptotic notation. Recursion, array and list manipulation, searching and sorting, and the standard data structures dominate the question bank.
Core rules
- Big-O is an upper bound, Ω a lower bound, Θ a tight bound. State precisely which one the question asks for.
- Reference costs: linear search O(n); binary search O(log n) but only on sorted data; bubble, insertion and selection sort O(n²); merge sort and heapsort O(n log n); quicksort Θ(n log n) average and O(n²) worst case; hash lookup O(1) average, O(n) worst case.
- Every recursion needs a base case and a step that moves towards it; otherwise the call stack overflows.
- Stack is LIFO, queue is FIFO. In-order traversal of a binary search tree yields sorted output; a balanced BST has height Θ(log n).
- Tracing discipline: keep a table of variables and update it line by line, and note whether parameters are passed by value or by reference.
Worked example
for i ← 1 to n
for j ← 1 to i
s ← s + 1
The inner loop runs i times, so the total is 1 + 2 + … + n = n(n+1)/2 = Θ(n²). A second item: binary search in a sorted array of 1,000,000 keys needs at most ⌈log₂(1,000,001)⌉ = 20 comparisons, since 2¹⁹ = 524,288 and 2²⁰ = 1,048,576. Third: with f(n) = f(n−1) + n and f(0) = 0, tracing gives f(4) = 4 + 3 + 2 + 1 = 10, which is Θ(n²), not exponential.
Traps that cost marks
Reporting O(n²) for n(n+1)/2 when Θ(n²) is requested, or vice versa; assuming quicksort is always n log n; counting loop iterations from 0 when the pseudocode starts at 1; forgetting that binary search requires sorted input; and mis-tracing a recursive call whose return value is combined after the recursive call returns.