Motivation
A program returning plausible answers on several examples is evidence, but does not establish correctness for every legal input. Likewise, a short program need not run quickly. Algorithm analysis separates two questions: whether the result satisfies a specification, and how much work is required as the input grows. A useful proof states the input assumptions, tracks exactly what remains true during execution, and explains why execution ends.
Arrays use zero-based indices. Unless stated otherwise, comparisons and operations on array indices take constant time in a random-access machine model, and array elements can be compared in constant time. Later complexity statements depend on these assumptions.
Definitions
Definition 1.1.1
(Specifications and correctness)
A precondition describes legal inputs and any assumed initial state. A postcondition describes the required result. An algorithm is partially correct if every terminating execution starting from the precondition satisfies the postcondition. It is totally correct if it is partially correct and every such execution terminates. A loop invariant is a statement true before the first iteration and preserved by every iteration that executes.
To use an invariant, prove initialization and preservation, then combine it with the negation of the loop condition to obtain the postcondition. An invariant need not itself be the postcondition: it must describe intermediate states where work remains. A variant for termination is a nonnegative integer that decreases strictly on every iteration. Merely saying that a variable changes is insufficient; it might increase without bound or oscillate.
Definition 1.1.2
(Asymptotic bounds and the input-size convention)
For eventually nonnegative functions, means that some constants satisfy for all . Write for the reverse bound up to a positive constant, and when both hold. The constants cannot depend on . A worst-case running time maximizes the cost over all legal inputs of size ; a best-case or average-case assertion is a different claim requiring its own definition.
Input size must be stated. A list of fixed-size keys has size proportional to , while a positive integer written in binary needs bits. An algorithm performing iterations is not polynomial in the bit length just because it is linear in the numeric value. Addition on arbitrarily long integers is also not automatically a unit-cost operation. A model is part of a theorem, rather than a detail to infer after seeing its conclusion.
Theorems
Theorem 1.1.3
(Binary search with a half-open interval)
Let be sorted in nondecreasing order, and let be a target. The following algorithm returns an index containing if one exists, and otherwise returns NOT_FOUND. It terminates after iterations and uses constant auxiliary space.
lo = 0; hi = n
while lo < hi:
mid = lo + floor((hi - lo) / 2)
if A[mid] < t:
lo = mid + 1
else if A[mid] > t:
hi = mid
else:
return mid
return NOT_FOUND
Theorem 1.1.4
(Merge sort)
A recursive algorithm that sorts each half of an array and then merges the sorted halves returns a sorted permutation of the input. With a merge that reads and writes a linear number of elements, its worst-case running time is for , and a standard array implementation uses auxiliary storage beyond the input, plus an recursion stack.
Proof sketch or proof idea
Proof
(Binary search: invariant and termination)
For binary search, maintain and the assertion that, if the target occurs anywhere, it occurs at some index in the half-open interval . Initially the whole array is available. When , sortedness excludes every index at most , so changing preserves the assertion. When , sortedness excludes every index at least , so changing preserves it. Equality returns a valid index immediately. If the loop exits normally, the interval is empty, so the invariant implies that the target never occurred.
The integer length decreases strictly on each non-returning iteration and remains nonnegative. Indeed, when the loop executes, so each update removes at least or the portion including it. The new length is at most the floor of half the old length. Thus there are at most iterations when , and none when . The midpoint expression also avoids forming , although fixed-width integer overflow still requires a representation whose allowed index differences are safe. The stated algorithm does not search for the first occurrence among duplicates; that is a different specification.
Proof X-ray
Correctness and termination close different gaps
The binary-search invariant says where an existing target must remain; it does not by itself force the loop to stop. The decreasing interval length supplies that missing argument. Conversely, a shrinking interval proves termination without proving that discarded positions were safe to remove. The proof succeeds only when preservation and decrease are both checked against each branch of the algorithm.
Proving the merge operation
Proof
(Merge returns a sorted permutation)
Suppose the two input sequences and are already sorted. Maintain pointers to their first unused elements and an output prefix. The invariant states that this prefix is sorted and contains exactly the elements already consumed, with their multiplicities, and that every output element is at most every unused element. Initially the prefix is empty. Select the smaller current head, taking the left one on a tie, and append it. Each head is least in its own remaining sequence, so the chosen head is least among all remaining elements. The invariant is preserved. Once one sequence is exhausted, append the other remainder, which is already sorted and no smaller than the output prefix.
The number of unused elements decreases every time an element is appended, proving termination. The final output is sorted and contains all input elements with their original multiplicities. A proof of sortedness alone would be inadequate: an algorithm that discards every key also returns a sorted sequence. Choosing the left head on equality additionally preserves the relative order of equal keys from the two halves, giving stability if both recursive sorts are stable.
Recursive correctness and the recurrence
Proof
(Merge sort: induction and the recurrence)
Prove merge sort correct by strong induction on . Empty and one-element arrays are already sorted permutations. For , both halves have smaller sizes, so the induction hypothesis supplies sorted permutations of those halves. The merge proof then supplies a sorted permutation of their concatenation. This is the recursive counterpart of a loop-invariant proof; recursive calls do not justify themselves without a smaller parameter and a base case.
For powers of two, the time recurrence is up to constant-factor bounds, with constant base cost. At recursion level there are subproblems of size , so their total nonrecursive work is proportional to . There are non-leaf levels, and the leaves contribute only linear work. Summing gives the claimed order. For arbitrary , floor and ceiling halves produce a tree of depth at most , with at most linear total merge work per level, proving the upper bound. For a lower bound, each of the first levels consists of subarrays of length at least two whose total length is , and merging them costs at least linear copying work. Their sum is . This lower bound refers to the stated merge implementation, not to every conceivable sorting algorithm.
Space, recurrences, and what is being counted
The runtime recurrence adds the costs of both recursive calls because both execute. Peak auxiliary memory is different: the calls can run sequentially, reusing a single temporary array. A temporary buffer of length suffices, while at most logarithmically many activation records coexist. Summing the storage allocated over the entire run would measure total allocation, not peak live memory. These two quantities need not agree.
A recurrence is useful only after explaining its terms. Dividing into two pieces does not automatically produce logarithmic time; binary search follows one branch, while merge sort follows both. A recurrence of the form sums an arithmetic series and gives quadratic growth, even though each recursive call handles a smaller input. Likewise, an extra linear-time copy at every merge-sort call changes a constant factor, while a quadratic merge step changes the asymptotic order. The algorithm determines the recurrence, not the other way around.
Concept lensAnalytic
The recurrence solved exactly
Merging lists of lengths and takes at most comparisons, so for the worst-case comparison count satisfies with . Each of the levels contributes minus the number of merges at that level, and the merges number in all, so
For this is , matching an exhaustive check over all inputs. The order is thus an exact formula with an explicit linear correction.
Worked examples
Worked example 1.1.5
(An unsuccessful search still has a proof)
Search for five in . The first interval is with midpoint two and value four, so update to . Its midpoint four contains nine, giving . The midpoint three contains eight, giving and failure. The invariant rules out all eliminated positions at each stage; failure is therefore a correct result, rather than an exceptional state.
Worked example 1.1.6
(Insertion sort and the difference between bounds)
At the start of iteration , insertion sort maintains that the prefix of length is a sorted permutation of the original prefix. Inserting the next key by shifting larger prefix keys preserves this property and eventually sorts the whole array. An increasing input needs only one failed comparison per insertion, giving linear work in a standard implementation. A decreasing input shifts keys, giving quadratic worst-case work. Saying insertion sort is quadratic describes its worst case, not every input.
Worked example 1.1.7
(Numeric value versus binary length)
Consider a loop that counts from zero to a positive input integer . If , the input has bits and the loop performs iterations. This is exponential in the bit length. Calling it linear is meaningful only when the parameter is the numeric value , and does not establish a polynomial-time algorithm on binary integers. If the counter itself has growing size, bit-operation accounting can increase the cost further.
Common mistakes
Counterexample mode
Binary search on an unsorted array
A tempting claim is that the loop finds a target whenever it occurs in the array. Take and . With and , the midpoint is and , so . Then and , so and the loop exits with NOT_FOUND, although . The invariant step that fails is the use of sortedness: " excludes every index at least " holds only if is nondecreasing, and here it discards index . The repair is the precondition itself: the array must be sorted in nondecreasing order before the search starts.
Common mistake
(Proving only the successful branch)
An invariant must survive every legal branch, including equality and empty-input cases. Testing only successful searches leaves the failure specification unproved. A termination proof should use a quantity with a lower bound, not merely state that the search region changes.
Common mistake
(Reading big-O as equality or worst case)
Big-O is an upper bound, not an equality or a synonym for worst case. A constant-time function is also , though that is an uninformative bound. Logs of different fixed bases differ by a constant factor; their bases matter for exact counts but not for a classification. Avoid treating an average-case claim as a worst-case guarantee without specifying an input distribution.
Summary
Correctness needs a specification, preservation argument, and termination argument. Running time needs a cost model, an input-size definition, and justified counting. Binary search shrinks one candidate interval; merge sort solves both halves and pays to combine them. Their different recurrences express different executed work, despite a shared divide-and-conquer idea.
Exercises
Quick check
(Modify the binary-search specification to find the first index with , returning if none exists. Give an invariant and explain both updates.)
State what must be true about the indices below and at least .
Solution · Guided solution
Maintain that every index below has value less than , and every index at least has value at least , with . Start at zero and , where both outside regions are empty. If , set ; otherwise set . Sortedness proves preservation, and interval length decreases as before. On exit separates the two regions, hence is the first qualifying index or . Equality must take the second branch to retain earlier equal keys.
Quick check
(Solve and for powers of two, with positive constant base costs.)
Count the levels of the recursion and the cost per level.
Solution · Answer
For , the first recurrence expands through calls, giving a constant plus , so for . For the second, each of the internal levels costs , and the leaves cost a constant each, giving .
Quick check
(A programmer claims that checking sortedness of the output proves a sorting algorithm correct. Give a counterexample and the missing postcondition.)
Think of an algorithm that is trivially sorted but useless.
Solution · Answer
Returning the empty array on every input always returns something sorted. It fails to preserve the input elements. The missing condition is that the output is a permutation of the input, including multiplicities; output length alone would still allow replacement by unrelated equal keys.
Quick check
(Prove that , giving explicit constants for .)
Compare and with .
Solution · Answer
For , , because and . Thus lower constant three, upper constant fourteen, and threshold one prove the assertion.