Algorithms and Problem Solving
Algorithms and Problem Solving tests your ability to design, trace, and compare procedures. You should be able to follow pseudocode, identify loop invariants, estimate growth rates, and choose a suitable search or sort for a stated constraint.
Searching and sorting
Linear search checks each item in turn: O(n) worst case and works on unsorted data. Binary search repeatedly halves a sorted search interval: O(log n), but it requires sorted data and random access. Bubble sort repeatedly swaps adjacent out-of-order items: O(n²) worst case. Selection sort finds the minimum remaining item each pass: also O(n²), with fewer swaps. Merge sort divides and merges: O(n log n) but needs extra space.
Complexity
Big-O describes an upper bound on growth as input size grows, ignoring constants and lower-order terms. O(2n+5) simplifies to O(n); O(n²+n) simplifies to O(n²). Big-O does not tell you the exact running time on a particular machine. Space complexity counts extra memory, not the input itself unless stated.
Worked example
Search for 23 in the sorted list [3, 8, 12, 19, 23, 31, 40]. Low=0, high=6. Mid=3, value 19; 23>19, so low=4. Mid=5, value 31; 23<31, so high=4. Mid=4, value 23: found. Three comparisons. A linear search would need five.
Traps
Do not apply binary search to unsorted data. Count comparisons carefully: the midpoint is examined each iteration. O(log n) usually means base-2 halving in this context; the base is irrelevant asymptotically. Do not confuse best case with worst case. A flowchart decision must have a clear condition and both branches should lead toward termination.