1.4Algorithms & complexity

The previous section covered the "containers" for data. This section covers what you can do with those containers, and how efficiently: the two major algorithm families, search and sort, and Big-O notation, the objective yardstick for comparing efficiency. Much of Exam B's pseudocode content is built on this section, so the goal is not rote memorization but understanding deep enough to trace how each algorithm actually runs.

1.4.1Search algorithms

• Linear search is the simplest search: compare each element from the start, one by one, against the target. The data need not be sorted, but in the worst case every element must be checked, giving O(n) complexity.
• Binary search requires sorted data. It compares the target with the middle value of the search range and halves the range based on the comparison, repeating until found. Its O(log n) complexity is dramatically faster than linear search.

1.4.2Sorting algorithms

• Bubble sort repeatedly compares adjacent pairs and swaps them if out of order. It is simple to implement, but its O(n^2) complexity makes it unsuitable for large data.
• Quicksort picks a pivot, partitions elements into smaller and larger groups relative to it, and recursively sorts each partition (a divide-and-conquer approach). Its average complexity of O(n log n) is fast, but a poor pivot choice can degrade the worst case to O(n^2).
• Merge sort keeps splitting the data in half down to single elements, then progressively merges the sorted small runs back together (divide-and-conquer). Its complexity is consistently O(n log n), but it needs extra memory for the merge step.

1.4.3Recursion and Big-O notation

• Recursion is a technique where a routine calls itself. It naturally expresses problems that break down into "the same problem, but smaller" (e.g., quicksort, merge sort, factorial). A base case (termination condition) is essential—without one, the calls continue forever.
• Big-O notation expresses how an algorithm's running time or memory use grows as the input size n increases. It ignores constant factors and lower-order terms, focusing only on the dominant growth trend.
• A representative ordering of growth: O(1) < O(log n) < O(n) < O(n log n) < O(n^2). As n grows, the gap between these widens dramatically (e.g., at n = 1,000,000, O(log n) is about 20, while O(n^2) is one trillion).

Consider an e-commerce site that needs to speed up looking up a specific product ID among one million products. Currently it uses linear search, checking items one by one from the start, requiring up to one million comparisons in the worst case (O(n)). If the product IDs are pre-sorted in ascending order, binary search becomes possible, cutting the worst-case comparison count to roughly 20 (log2(1,000,000) ≈ 20, i.e. O(log n)). But using binary search means maintaining the "sorted" precondition continuously, so you must weigh that against the cost of keeping the data sorted as new products are added. Next, consider how to do that sorting. If the data volume is small and implementation simplicity matters most, bubble sort (O(n^2)) may be acceptable, but at a scale of one million items it would take an unrealistic amount of time. The realistic choices are the consistently fast merge sort (always O(n log n)) or the average-case-fast quicksort (average O(n log n), worst case O(n^2)): under tight memory constraints, a quicksort with a carefully chosen pivot strategy is attractive, while if extra memory is available and worst-case stability matters more, merge sort is the better fit. Both merge sort and quicksort internally share the same design (divide-and-conquer): split a big problem in half, solve the smaller same-shaped problems via recursion, and combine the results—and every recursive design must include a base case that stops splitting once the element count reaches one or fewer. In short, the choice of search method, the choice of sorting algorithm, and the recursive implementation are all decisions grounded in efficiency estimated via Big-O notation.

1.4.4Section summary

• Linear search = O(n) (no sorting needed); binary search = O(log n) (requires sorted data)
• Bubble sort = O(n^2); merge sort = always O(n log n); quicksort = average O(n log n), worst case O(n^2)
• Big-O notation expresses the dominant trend in efficiency as input size grows. Recursion requires a base case