1.4Algorithms & time complexity

Having covered the complexity characteristics of each data structure, this section evaluates the efficiency of the algorithms that operate on them. AP does not test reading pseudocode to determine complexity (that is Exam B territory), but comparing efficiency via Big-O notation and choosing the right technique for the situation is an important topic tested in Exam A.

1.4.1Big-O notation

• Big-O notation expresses the growth trend of processing time (or memory) as input size n increases. It ignores constant factors and lower-order terms, keeping only the dominant term (e.g., 3n^2+5n+2 is O(n^2)).
• The representative orders, from smallest to largest, are O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n). The gap becomes dramatic as input size grows—for example, at n=1,000,000, O(n) needs a million operations while O(n^2) needs a trillion.

1.4.2Search algorithms

• Linear search compares elements one at a time from the start; it needs no sorting but is O(n). Binary search repeatedly compares against the middle value of sorted data to halve the search range, achieving O(log n)—but it requires the data to already be sorted.
• Hash-based search is, as covered in the previous section, average O(1), but binary or linear search can be more practical when the element count is small or memory is tightly constrained.

1.4.3Sorting algorithms and stability

• Quicksort recursively partitions elements into those smaller and larger than a pivot value. It is O(n log n) on average, but a poor pivot choice (e.g., always picking the first element on already-sorted data) can degrade it to O(n^2) in the worst case.
• Merge sort splits the data in half, sorts each half, then merges them. It always guarantees O(n log n), but the merge step requires extra memory equal to the size of the original data.
• Heapsort repeatedly extracts the max (or min) element using the heap structure from the previous section. It always guarantees O(n log n) and needs almost no extra memory (in-place), which is its advantage.
• Stability is whether elements with equal keys retain their relative order before and after sorting. Merge sort is stable; quicksort and heapsort are (in their standard implementations) unstable. Stability matters in multi-key sorts—for example, "re-sorting name-sorted data by department should still preserve the name order within each department."

Consider a batch job that sorts one million sales records. Suppose quicksort is chosen, but because the data is already nearly sorted by date and the implementation always picks the first element as the pivot, the partitioning stays lopsided, and performance approaches the worst-case O(n^2) behavior, making the job abnormally slow. The fix is either to choose the pivot randomly or via a median approximation, or to switch to merge sort or heapsort, which always guarantee O(n log n). For a memory-constrained embedded batch, heapsort (needing almost no extra memory) is the reasonable choice; conversely, if memory headroom is available and there is a multi-key requirement such as "data sorted by name, then re-sorted by department code, should still preserve name order within each department," the stable merge sort is the appropriate pick. Now consider search: suppose a lookup for a specific sales ID against these one million records was always done via linear search (O(n)). If the data is sorted, simply switching to binary search cuts it to roughly log2(1,000,000) ≈ 20 comparisons—a dramatic speedup. Even for the same broad goals of "sorting" and "searching," the optimal algorithm depends on the data's properties (already sorted? memory-constrained? stability required?)—this practical judgment is exactly what level-3 questions test.

1.4.4Recursion, divide-and-conquer, dynamic programming, and graph search

• Recursion solves a problem by having a function call itself. Divide-and-conquer is a design strategy that splits a problem into smaller subproblems, solves each recursively, and combines the results (merge sort and quicksort are prime examples).
• Dynamic programming (DP) eliminates the waste of recomputing the same subproblem repeatedly by memoizing (recording and reusing) subproblem results. A naive recursive Fibonacci computation is O(2^n), but memoizing with DP reduces it to O(n).
• Breadth-first search (BFS) uses a queue to explore nodes nearer the source first, making it well suited to finding the shortest path (when edge weights are uniform). Depth-first search (DFS) uses a stack (or recursion) to go as deep as possible before backtracking, making it well suited to enumerating all paths or detecting cycles.

1.4.5Section summary

• Big-O notation keeps only the dominant term. Efficiency decreases in the order O(1)<O(log n)<O(n)<O(n log n)<O(n^2)
• Choose between quicksort (O(n log n) average, O(n^2) worst case, unstable) and merge sort/heapsort (always O(n log n))
• Dynamic programming memoizes subproblems to eliminate redundant work; BFS suits shortest-path search, DFS suits enumerating all paths or detecting cycles