Advanced level · Module 4: Testing and Performance in C++ · Lesson 3 of 4
Algorithms and Complexity in Practice
Use algorithmic complexity to make the biggest performance wins: better algorithms and data structures.
In this lesson you will
- Estimate the complexity of loops and container operations
- Replace slow algorithms and structures with faster ones
Key concepts
Big-O notationO(n²) vs O(n log n)hash lookupreserve()
The lesson
Complexity describes how running time grows with input size. A nested loop comparing every pair of items is O(n²): doubling the data quadruples the time. Sorting is O(n log n); a hash-map lookup is O(1) on average.
The largest speed-ups usually come from changing the algorithm: replacing repeated linear searches with a hash map, or sorting once and then scanning, instead of tuning individual lines.
Small changes also matter: vector::reserve avoids repeated reallocations when the final size is known, and passing large objects by const reference avoids copies.
Step by step
- Find an O(n²) duplicate check in the processor.
- Replace it with an unordered_set approach.
- Add reserve where the size is known.
- Benchmark before and after.
Practice activity
Optimise the hottest function identified in the previous lesson and report the measured speed-up with tests still passing.
Expected result: A measured, repeatable speed-up with all tests passing.
Check your understanding
-
What is the complexity of checking every pair of n items?
Show answer
O(n²).
-
What does vector::reserve do?
Show answer
Allocates capacity in advance to avoid repeated reallocations.
Taught live by an instructor — online or in person. Free course lessons are for self-study and do not lead to a certificate — see registration options.