Computational complexity
Objective. Compare elementary time and space growth.
- 1. Learn
- 2. Worked example
- 3. Practice
- 4. Feedback
- 5. Continue
Learn: the key idea
Computational complexity compares how the running time or memory use of an algorithm grows with input size n, expressed using big-O notation that ignores constant factors and lower-order terms. An algorithm is O(n) if its time grows proportionally to n, O(n²) if it grows like n squared (common in nested loops), and O(log n) if it halves the problem each step, as in binary search. For large n, an O(n log n) sorting algorithm vastly outperforms an O(n²) one, even though for small n the O(n²) algorithm might run faster due to smaller constants. Big-O describes asymptotic, not exact, behaviour.
Worked example
An algorithm performs n² comparisons for an input of size n; using computational complexity ideas, state its growth class and the number of comparisons when n = 20.
- 1Identify the complexity class: O(n²)
- 2Write the comparison count formula: n²
- 3Substitute n = 20
- 4Compute: 20² = 400
Answer: 400 comparisons, O(n²)
Concept mastery
Based on your past attempts at this lesson — the question types to practise again come first.
Complete a practice set to see your concept breakdown here.
Practice
Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.
Start practisingCommon mistake. Concluding that O(n²) is always slower than O(n) in practice; for small input sizes, constant factors can make the O(n²) algorithm faster. Big-O only describes growth trends for large n, not every case.
Your progress
Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.
0 of 5 steps complete
Your place saves automatically as you read.