Computer science · University
Algorithms, invariants and asymptotic costs · revision notes
An algorithm should have a stated input contract, output goal and termination argument. A loop invariant describes what remains true at a defined point in each iteration.
Key ideas and conditions
Correctness
An algorithm should have a stated input contract, output goal and termination argument. A loop invariant describes what remains true at a defined point in each iteration.
Growth
Big-O describes asymptotic upper growth bounds, not exact seconds on every machine. State the operation and input size being counted.
Search
Binary search requires a sorted sequence and consistent ordering. It reduces the remaining interval at each step.
Testing
Edge cases such as empty inputs, duplicate values and boundaries complement proofs; passing examples alone does not prove correctness.
Explain without looking
- Outline the three standard parts of a loop-invariant proof.
- A nested loop executes n times outside and n times inside each iteration. For n=7, count inner-body executions.
Further reading and review references
These are reference links, not copied exercises, institutional endorsement or proof of independent review.
AI-assisted preview; independent educational review required. Level labels describe prerequisites, not accreditation or official curriculum alignment.