Big-O Growth Rates

Lesson notes

Overview

How the work of an algorithm grows with input size n — the language of efficiency. This topic is rated advanced and is number 124 of 245 in Mathematics. Deeper models, formal results and harder reasoning.

What you are seeing

The panel above shows a graph of the function. Each slider changes one parameter, so you can see exactly how the curve bends, shifts or stretches. The animation is drawn live from the model, so everything you see responds to the sliders. Press Space to pause, use Restart to replay from the start, and change the speed to slow down quick events.

In depth

Big-O notation describes how the running time or memory of an algorithm grows with the input size n, ignoring constant factors. From slowest to fastest growth: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic, and then exponential. The differences are dramatic for large inputs: an O(n²) method on a million items needs a trillion steps. Choosing a better algorithm usually matters more than a faster computer.

Reading the relationship

The expression "O(1) < O(log n) < O(n) < O(n log n) < O(n²)" is a compact summary of the idea. It uses the symbols O, n; name what each one stands for before you start. Notice that it contains a squared term, so doubling that quantity changes the result by a factor of four, and a logarithm, which turns multiplication into addition and compresses large values. Then use the sliders to see how changing one quantity changes the others.

A guided exploration

1. Set every slider to its middle value and note the shape of the curve. 2. Move one slider at a time and describe whether the curve shifts, stretches or turns. 3. Find the value where the behaviour changes sharply, then connect it to the formula.

Try this

Try to explain why the pattern holds, not just what it is. Look for limiting cases and what happens at the edges.

Common pitfalls

A frequent slip is memorising the rule without the picture. If a result surprises you, sketch the graph or test a simple number by hand before trusting the algebra.

How it connects

It builds on “Venn Diagrams and Inclusion–Exclusion”, the topic before it in Mathematics. Once you are comfortable, continue with “Graph Theory Basics”.

Why it matters

Mathematical ideas like this one are the language that physics, engineering, computing and statistics are written in.