Complexity for Computer Sciences
Complexity, or algorithm analysis, measures how the time and memory an algorithm needs grow as input size grows. Big O notation describes an upper bound and ignores constants, so you can compare approaches before running them. It is the vocabulary used to justify choosing one algorithm or data structure over another.
Stage: Programming and Maths · Part of the Computer Science roadmap · Last reviewed 19 November 2026
What to learn in Complexity
- Derive the Big O running time of nested loops by counting operations
- Compare O(n), O(n log n) and O(n^2) growth for an input of one million items
- Solve a simple divide-and-conquer recurrence using the recursion tree method
- Distinguish best, average and worst case for a search algorithm
- Estimate space complexity including the recursion stack
Complexity interview questions
What is the difference between Big O, Big Omega and Big Theta?
Big O gives an upper bound on growth, Big Omega a lower bound, and Big Theta a tight bound where both match. People often say Big O informally when they mean the tight worst case, but the three describe different relationships to the running time function.
Why can an O(n) algorithm be slower than an O(n^2) one in practice?
Big O ignores constant factors and lower-order terms and describes growth for large n. For small inputs, an O(n^2) method with tiny overhead may beat a linear method with heavy constants or poor cache behaviour. Asymptotic analysis only wins as inputs get large.
Where Complexity fits in the Computer Science roadmap
Complexity belongs to the Programming and Maths stage (beginner level), which takes about 40 hours. Foundations.
Other units in this stage
Back to the full Computer Science roadmap