Algorithm Analysis: Correctness, Complexity & Invariants

1. Problem and Motivation

Algorithm analysis answers two different questions. Correctness asks whether the algorithm always produces the required result. Efficiency asks how much time and memory it needs as the input grows. A fast algorithm that returns the wrong answer is useless; a correct algorithm that takes years on realistic input is also unusable.

Suppose a system must find the largest value in an array. The task sounds simple, but a production decision still depends on questions such as: can the input be empty, are values duplicated, does the data arrive as a stream, and must the original array remain unchanged? Analysis turns those questions into explicit assumptions and guarantees.

2. Prerequisites and Vocabulary

This lesson assumes basic arrays, loops, functions, and mathematical notation. The central vocabulary is:

• Input size: usually written as $n$, but it can be rows, bits, vertices, queries, or another meaningful measure.
• Operation count: a machine-independent estimate of dominant work such as comparisons, probes, or element moves.
• Invariant: a statement that remains true at a precise point in every loop iteration.
• Asymptotic bound: a statement about growth, such as $O(n)$, $\Omega(n)$, or $\Theta(n)$.
• Amortized cost: the average cost per operation over a sequence, even when individual operations vary.

3. A Small Concrete Example

The trace exposes the key invariant: after processing the first $k$ values, best is the maximum of exactly those $k$ values.

4. Brute Force and Its Limit

A brute-force maximum algorithm can compare every element against every other element. It is correct, but it repeats work: once a value has been shown smaller than another value, that fact is not reused efficiently. Its comparison count grows quadratically, $\Theta(n^2)$.

The one-pass algorithm keeps only the best answer seen so far. It performs one comparison per remaining element, so its time is $\Theta(n)$ and its extra space is $\Theta(1)$. This is the recurring pattern of analysis: write down the obvious method, identify repeated work, then name the information that can be retained.

5. Core Insight and Plain-English Steps

1. Reject an empty input or define an explicit empty-input result.
2. Initialize the current best value from the first element.
3. Scan each remaining element once.
4. If the current value is larger, replace the stored best value.
5. Return the stored value after the scan.

Pseudocode

maximum(A):
    if length(A) = 0:
        return EMPTY_INPUT

    best = A[0]
    for each value in A starting at index 1:
        if value > best:
            best = value
    return best

6. Correctness and Loop Invariants

Use a loop invariant with three parts:

1. Initialization: before the first iteration, best equals the maximum of the one-element prefix.
2. Maintenance: if best is the maximum of the processed prefix, comparing it with the next value makes it the maximum of the longer prefix.
3. Termination: when the loop ends, every element has been processed, so best is the maximum of the entire array.

This proof is short because the state was chosen well. A useful invariant is not a comment added after coding; it is a design tool that tells us what information must survive each iteration.

7. Complexity Analysis

The algorithm reads every element after the first, so it performs exactly $n-1$ comparisons for a non-empty input. Therefore:

Because the upper and lower bounds match, the algorithm is asymptotically optimal: its running time is $\Theta(n)$. Notice what $n$ represents here: the number of values, not the numeric magnitude of the values.

8. Three-Language Implementation

Each panel is a complete program with the same input, behavior, validation, and output. The implementations deliberately reject empty input instead of silently returning a fabricated maximum.

def maximum(values):
    if not values:
        raise ValueError("maximum is undefined for an empty sequence")
    best = values[0]
    for value in values[1:]:
        if value > best:
            best = value
    return best

sample = [7, 2, 9, 4]
print("Maximum:", maximum(sample))  # Maximum: 9

#include <iostream>
#include <stdexcept>
#include <vector>

int maximum(const std::vector<int>& values) {
    if (values.empty()) {
        throw std::invalid_argument("maximum is undefined for an empty sequence");
    }
    int best = values[0];
    for (std::size_t index = 1; index < values.size(); ++index) {
        if (values[index] > best) {
            best = values[index];
        }
    }
    return best;
}

int main() {
    std::vector<int> sample{7, 2, 9, 4};
    std::cout << "Maximum: " << maximum(sample) << '\\n';
}

import java.util.List;

public class MaximumValue {
    static int maximum(List<Integer> values) {
        if (values.isEmpty()) {
            throw new IllegalArgumentException("maximum is undefined for an empty sequence");
        }
        int best = values.get(0);
        for (int index = 1; index < values.size(); index++) {
            if (values.get(index) > best) {
                best = values.get(index);
            }
        }
        return best;
    }

    public static void main(String[] args) {
        List<Integer> sample = List.of(7, 2, 9, 4);
        System.out.println("Maximum: " + maximum(sample)); // Maximum: 9
    }
}

9. Recurrences, Amortization and Lower Bounds

Recurrences and the Master Theorem

Divide-and-conquer algorithms describe their work with recurrences. Merge sort, for example, splits into two half-size problems and spends linear time merging:

$$T(n) = 2T(n/2) + \Theta(n)$$

The recursion tree has $\log_2 n$ levels, with $\Theta(n)$ work per level, giving $T(n)=\Theta(n\log n)$. The recurrence is more informative than memorizing the final bound because it exposes where the work happens.

When the Master Theorem Is Not Enough

The Master Theorem handles recurrences of the form $T(n)=aT(n/b)+f(n)$, but some divide-and-conquer algorithms use unequal subproblem sizes. The Akra-Bazzi method extends the analysis to recurrences such as $T(n)=T(n/2)+T(n/3)+n$. First solve $\sum_i a_i b_i^p=1$ for $p$, then combine that exponent with the non-recursive work using the Akra-Bazzi integral. The important lesson is to identify the recurrence shape before choosing a theorem.

Amortized Analysis

A dynamic array append is usually constant time, but occasional resizing copies many elements. Aggregate analysis spreads the expensive resize over the cheap appends. If capacity doubles, the total number of copied elements across $n$ appends is less than $2n$, so the amortized append cost is $O(1)$ even though one individual append can cost $O(n)$.

Lower Bounds and Expected Work

A lower bound describes work no algorithm in a defined model can avoid. In the comparison model, an algorithm learns about input order only through comparisons. A comparison tree for sorting must have at least $n!$ leaves, one for each possible input order, so its height is at least $\lceil\log_2(n!)\rceil=\Omega(n\log n)$. This explains why comparison sorting cannot asymptotically beat $\Omega(n\log n)$, while counting and radix sort can avoid that bound by using operations outside the comparison model.

Randomized algorithms require a separate analysis of expected complexity: average the running time over the algorithm's random choices for a fixed input, and separately state the probability of an incorrect result when one exists. Randomized quicksort is Las Vegas with expected $O(n\log n)$ time and always-correct output; a sampling-based estimator may be Monte Carlo, with bounded runtime but a nonzero error probability.

Cache Awareness

Asymptotic complexity abstracts machine details, but memory access still affects real performance. A sequential array scan has predictable access and good locality; a pointer-heavy structure may perform the same number of abstract operations while causing more cache misses. Treat cache behavior as a second lens, not a replacement for asymptotic analysis.

10. Applications and Alternatives

Compare alternatives by the operation that matters. A prefix sum gives $O(1)$ static range queries after $O(n)$ preprocessing; a Fenwick tree supports updates in $O(\log n)$; a segment tree supports richer associative queries and range updates at a higher implementation cost. The best algorithm is defined by the workload, not by the shortest code.

11. Exercises and Mastery

Easy

1. Write a minimum-value scan and state its invariant.
2. Count comparisons for an input of length 1, 2, and $n$.

Medium

1. Return both the minimum and maximum in one pass and compare its operations with two separate scans.
2. Design an invariant for insertion sort's outer loop.

Hard

1. Prove the amortized $O(1)$ append cost of a doubling dynamic array with aggregate analysis.
2. Derive the recurrence and complexity of a divide-and-conquer maximum algorithm.

Review rhythm: tomorrow, reconstruct the invariant and complexity without notes; next week, implement the scan in all three languages; several weeks later, identify the same summary-state idea in a new streaming problem. Finally, teach the distinction between correctness, upper bounds, lower bounds, amortized cost, and cache behavior to someone who knows basic loops.

12. Summary Cheat Sheet

• Correctness comes from a precise invariant, proof, and termination argument.
• Complexity measures growth in a meaningful input-size parameter.
• $O$ is an upper-bound convention, $\Omega$ is a lower bound, and $\Theta$ means matching growth.
• Recurrences expose divide-and-conquer structure.
• Amortized analysis spreads occasional expensive work across a sequence.
• Lower bounds tell you when further optimization is impossible in a chosen model.
• Cache locality, allocation, and branch behavior explain practical differences beyond asymptotic notation.