Foundations
The models, the measures and the proof methods that the rest of the site uses.
- Models of computation
- Asymptotic analysis
- Recurrences
- Correctness and invariants
- Amortized analysis
- Probabilistic analysis
- Lower bounds
Concepts
- Loop invariant
A statement about the variables of a loop that is true before each step. It is the main tool to prove that a loop is correct.
intro
Definitions
- Asymptotic notation
The notations O, Ω and Θ compare the growth of two functions for large inputs and ignore constant factors.
intro
Models
- Comparison model
A model where an algorithm learns about its input only by comparing two items. The cost is the number of comparisons.
intro