Foundations

Algorithms are not evaluated only by whether they appear to work. We need a model of the computation, a contract for the result, a correctness argument, and a way to describe resource growth.

Learning objectives

After this section, you should be able to:

• state preconditions and postconditions;
• use loop invariants to explain correctness;
• distinguish upper, lower, and tight asymptotic bounds;
• solve common recurrence relations; and
• explain why memory layout can affect real performance without changing a Big-O bound.

Core sequence

1. Correctness and invariants
2. Asymptotic analysis
3. Recursion and recurrences
4. Memory and locality

Important

Big-O notation is not a stopwatch. It describes how resource use grows under a stated model; constants, input distributions, allocation, cache behavior, and runtime optimizations still matter in programs.