Computer Science › Section F · Algorithms › Topic F.6
Efficiency and correctness
Two questions decide whether an algorithm is any good: how its running time grows as the input grows, and whether it really does what it claims for every input. This topic shows how to count steps, classify growth with big-theta notation, and prove a loop correct with an invariant.
In this topic
- Why efficiency still matters
- Worked example: searching 50,000 records
- Best, worst and average cases
- Analysing insertion sort
- Growth rates and big-theta notation
- Comparing the classes
- Correct, or only believed correct?
- Preconditions, postconditions and assertions
- Loop invariants
- Worked example: proving a loop correct
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…