How to use Big-O notation

Big-O notation answers one question: how does the runtime grow as the input size n grows?

Common classes

| Class | Meaning | Example | |---|---|---| | $O(1)$ | Constant time | Array lookup by index | | $O(\log n)$ | Halves each step | Binary search | | $O(n)$ | One pass | Linear search | | $O(n^2)$ | Nested passes | Bubble sort |

How to spot it

• A single loop over n items → $O(n)$.
• Nested loops, each over n → $O(n^2)$.
• Halving the search space each step → $O(\log n)$.

Big-O ignores constants: $2n + 3$ is still $O(n)$. Practise on randomised complexity questions below.