06 — Algorithms and Correctness

Specifications: What an Algorithm Must Promise

An algorithm is a finite, precise procedure for solving a problem. Its specification describes what result must be produced, while its implementation describes how the result is produced. Separating these ideas allows different implementations to satisfy the same behavioral promise.

A useful specification identifies:

• Inputs: the data supplied to the procedure.

• Outputs: the result that must be returned.

• Preconditions: facts that must hold before execution.

• Postconditions: facts guaranteed after successful execution.

• Termination condition: the reason the process eventually stops.

• Resource requirements: how running time and memory use grow.

For a search procedure, a postcondition might say that the result is $-1$ exactly when the target is absent; otherwise, the returned index identifies an element equal to the target. This is more precise than merely saying that the procedure “looks for” a value.

Takeaway: A correctness claim is meaningful only when the inputs, assumptions, expected result, and stopping behavior are specified clearly.

Searching: Linear and Binary Methods

Searching locates a target in a collection, but the best method depends on whether the collection is ordered.

Linear search checks elements from left to right until it finds the target or exhausts the collection. It works without sorting. For the list $[8, 3, 11, 4]$ and target $11$, it checks $8$, then $3$, and then returns index $2$. With $n$ elements, its worst-case running time is $\mathrm{O}(n)$.

Binary search requires a sorted collection. It compares the target with the middle element, then keeps only the half that might still contain the target. Each unsuccessful comparison approximately halves the remaining interval, producing running time $\mathrm{O}(\log n)$. For example, when searching for $17$ in $[2,5,8,12,17,21,30]$, a comparison with $12$ eliminates the left half, and a later comparison finds the target.

Binary search is not automatically faster overall if the data must first be sorted. It is most attractive when the collection is already sorted or will be searched repeatedly.

Takeaway: Linear search trades simplicity and no ordering requirement for $\mathrm{O}(n)$ worst-case time; binary search trades a sorted-input requirement for $\mathrm{O}(\log n)$ search time.

Sorting: Simple and Divide-and-Conquer Strategies

Sorting rearranges values according to a chosen order, such as increasing numerical order or alphabetical order. A sorting specification should also state whether the original collection changes, how duplicates are handled, whether equal records retain their relative order, and how much additional memory is used.

Insertion sort maintains a sorted prefix. It removes the next unsorted value and shifts larger prefix values one position to the right until the value can be inserted. Starting with $[5,2,4,6]$, the sorted prefixes become $[5]$, $[2,5]$, $[2,4,5]$, and finally $[2,4,5,6]$. It uses $\mathrm{O}(1)$ extra space and has worst-case time $\mathrm{O}(n^2)$, but it can perform well on small or nearly sorted inputs.

Merge sort uses divide and conquer. It divides the collection, recursively sorts each half, and merges the sorted halves by repeatedly choosing the smallest remaining value. There are approximately $\log n$ levels of division, and each level processes $n$ values during merging, so the running time is $\mathrm{O}(n\log n)$. Its usual implementation uses $\mathrm{O}(n)$ additional space.

Takeaway: Choose a sorting method by considering input size, existing order, memory limits, duplicate handling, and whether stability matters.

Iteration and Loop-Invariant Proofs

Iteration repeats instructions with a loop. A correct loop must make progress toward a stopping condition. For example, a list-summing procedure can initialize a total to $0$ and an index to $0$, add the element at the current index, and increase the index by $1$ on each pass. Once the index reaches the list length, the loop stops.

A loop invariant makes the loop’s changing state easier to reason about. For insertion sort, a suitable invariant is: before iteration $i$, the subarray from index $0$ through index $i-1$ is sorted and contains exactly the values that originally occupied those positions.

The proof has three stages:

1. Initialization: Before the first iteration, the prefix contains one value and is therefore sorted.

2. Maintenance: Assuming the prefix is sorted, inserting the next value while shifting larger values preserves the invariant for the next iteration.

3. Termination: When the loop ends, the prefix is the entire collection, so the whole collection is sorted.

This reasoning proves the general behavior of the procedure rather than only confirming a few examples.

Takeaway: A loop invariant connects local updates to a global postcondition through initialization, maintenance, and termination.

Recursion, Induction, and Iterative Alternatives

Recursion solves a problem by calling the same procedure on a smaller instance. A correct recursive procedure needs a base case, a recursive case that reduces the problem, progress toward the base case, and a way to combine the smaller result.

Factorial illustrates the pattern:

For input $3$, the calls reduce from $3$ to $2$, then $1$, and finally $0$. The base case returns $1$, after which the pending multiplications produce $6$.

Many recursive procedures have iterative equivalents. Recursion can express trees, nested structures, and divide-and-conquer methods naturally, while iteration often uses less call-stack memory for repetitive processes.

Recursive correctness is commonly established by mathematical induction: prove the base case, assume correctness for a smaller input, and show that the recursive step uses that result to solve the current input.

Takeaway: Recursion is correct only when every call moves toward a directly solvable base case and the returned smaller solution is combined correctly.

Termination, Total Correctness, and Review

Correctness has two separate parts. Partial correctness means that if an algorithm terminates, its output satisfies the specification. Termination means that the algorithm eventually stops. Together, they establish total correctness.

A common termination argument uses a variant: a nonnegative quantity that strictly decreases on every loop iteration or recursive call. Examples include the number of unprocessed elements, the size of a binary-search interval, the current value of $n$ in factorial, or the number of unsorted positions.

For binary search, the interval between the lower and upper bounds becomes smaller after every unsuccessful comparison. A finite interval cannot shrink forever while remaining nonempty, so the procedure terminates. For factorial, the argument decreases by $1$ on every recursive call until it reaches $0$.

A practical review should ask:

• Are inputs, outputs, preconditions, and postconditions precise?

• Are empty collections, duplicates, and boundary cases handled?

• Does every loop or recursive call make progress?

• What invariant or induction hypothesis supports correctness?

• What are the running-time and memory requirements?

• Do tests include ordinary, boundary, and error-revealing cases?

Testing can expose bugs, but it cannot prove correctness for every possible input. Specifications, invariants, induction, and termination arguments provide stronger guarantees.

Takeaway: Reliable algorithm design combines a precise specification, a correctness argument, a termination argument, and an efficiency analysis.