This chapter introduces the fundamental framework for designing and analyzing algorithms using two sorting algorithms—insertion sort and merge sort—as case studies. It establishes key concepts including pseudocode conventions, loop invariants for proving correctness, the RAM computational model, worst-case analysis, order of growth, and the divide-and-conquer paradigm.
Pseudocode conventions: The book uses a pseudocode similar to C/Java/Python with indentation-based block structure, 1-indexed arrays, dot notation for attributes (e.g., A.length), pass-by-value semantics (but pointers to arrays/objects are copied), short-circuit boolean operators, and sentinel values.
Loop invariants: A formal technique for proving algorithm correctness, requiring three properties:
Initialization: The invariant is true before the first iteration.
Maintenance: If true before an iteration, it remains true before the next.
Termination: When the loop ends, the invariant yields a useful correctness property.
RAM model: The Random Access Machine model assumes a single processor executing instructions sequentially, with constant-time arithmetic, data movement, and control operations. Word size is c lg n bits for constant c ≥ 1.
Input size: Depends on the problem—number of items for sorting, number of bits for integer multiplication, or vertices and edges for graph problems.
Running time: The number of primitive operations (steps) executed, where each line of pseudocode takes constant time cᵢ.
Worst-case vs. average-case analysis: The book primarily focuses on worst-case analysis because it provides a guaranteed upper bound, worst cases occur frequently in practice, and the average case is often roughly as bad as the worst case.
Order of growth: Focuses on the leading term of the running time formula, ignoring lower-order terms and constant coefficients. Uses Θ-notation informally (formalized in Chapter 3).
For j = 2 to A.length:
Store key = A[j]
Scan backward through A[1..j−1], shifting elements greater than key one position right