Guide · Algorithms · Algorithm complexity
Algorithm Complexity – Learning Guide
A correct solution is not enough – it must also be fast enough. This area teaches how to estimate the speed of a program before running it and how to turn a slow solution into a fast one.
It starts with O-notation and reading the limits from the task statement, continues with formulas that replace loops and ends with typical optimizations.
- Grades 6–8 and secondary school
- C++
- Competition preparation
n. From them, before writing the code, you can see whether a loop is enough, whether you need sorting or whether there is a formula – see the table in the lesson Algorithm complexity (SR).
Some lessons linked below are available only in Serbian for now. They are marked (SR).
1 Complexity
How the speed of an algorithm is measured and estimated.
2 Formulas instead of loops
When the result of a loop can be computed right away.
Replacing iterations with a formula (SR)
An arithmetic sequence, combinatorial formulas, segments in a binary string.
Open lesson →Formulas for sums and counting (SR)
Sums, numbers divisible in an interval, inclusion–exclusion, counting by groups.
Open lesson →Replacing iterations with a formula – tasks (SR)
A collection of tasks in which a formula replaces a loop.
Open lesson →3 Speeding up solutions
Typical ways to speed up a slow solution.
Suggested order
Useful external resources
- USACO Guide – Time Complexity – complexity with examples
- CSES Problem Set – "Introductory Problems" – tasks in which a formula replaces a loop
