Big-O & Growth Rates

Two programs can both be correct while one answers in a blink and the other runs until next week. Big-O lets you tell which is which before you write a single line.

beginner⏱ 12 min read

←Builds on

This is the starting point: no earlier topic is needed.

Leads to→

0Recursion & the Call StackCounting the calls in a recursion tree is how you price a recursive function.1Arrays & Dynamic ArraysAmortised O(1) push_back is a Big-O argument about many operations taken together.1Hash Tables: Sets & MapsAverage O(1) versus worst case O(n) is exactly the distinction Big-O taught you to make.1Prefix Sums, Two Pointers & Sliding WindowBoth tricks turn O(n²) nested loops into a single O(n) pass.2Elementary SortsCounting comparisons in two nested loops shows why these sorts are O(n²).2Binary Search & Search on the AnswerHalving the range every step is exactly where O(log n) comes from.3Monotonic StackEach element is pushed and popped once, so the total is O(n) despite the inner loop.4Generating Subsets & Permutations2ⁿ subsets and n! permutations show how fast exponential growth explodes.9GCD & the Sieve of EratosthenesEuclid's O(log n) and the sieve's O(n log log n) are growth rates worth recognising.11Naive Pattern MatchingCounting comparisons gives O(n·m) and shows where the work is wasted.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Count steps, not seconds

Seconds depend on your laptop, your language and your compiler. What does not change is how many basic steps the algorithm performs: a comparison, an addition, an array read.

So we describe the cost as a function of the input size n. A single loop over an array touches each element once: about n steps. A loop inside a loop touches every pair: about n × n steps.

For n = 6 that is 6 versus 36. For n = 100 000 it is a hundred thousand versus ten billion. The first finishes instantly; the second takes many seconds. The shape of the code tells you the shape of the cost.

02The growth rate ladder

A handful of functions cover almost every algorithm you will meet, from cheapest to most expensive:

O(1): constant, e.g. reading a[i]
O(log n): halving the problem each step, e.g. binary search
O(n): one pass over the data
O(n log n): good sorting algorithms
O(n²): all pairs, nested loops
O(2ⁿ): all subsets, brute force

On small inputs they look similar. As n grows, each rung leaves the one below it far behind: 2ⁿ shoots off the chart while log n barely moves.

n from 1 to 16; curves stop where they leave the chart.

03The two rules of Big-O

Big-O describes the growth for large n, so two simplifications are allowed:

Keep only the dominant term. In 3n² + 5n + 9, at n = 1000 the n² part is three million while the rest is about five thousand. The small terms stop mattering.
Drop constant factors. 3n² and n² grow the same way: double n and both become four times bigger. So 3n² + 5n + 9 is simply O(n²).

Rules of thumb for code: sequential blocks add (take the bigger one), nested loops multiply, and a loop that halves its range each time is O(log n). Memory is measured the same way: an extra array of size n is O(n) space.

04From constraints to algorithm

A typical computer does roughly 10⁸ simple steps per second. Combine that with the input limits in a problem statement and you can guess the intended complexity before you start:

n ≤ 20: exponential search over subsets is fine
n ≤ 5000: O(n²) passes
n ≤ 10⁶: you need O(n log n) or O(n)

Big-O usually talks about the worst case, the input that makes the algorithm work hardest. Some algorithms also have a better average case (quicksort) or an amortized cost (a growing array). And remember the limits of the model: for small n a "slower" O(n²) algorithm with tiny constants can beat a clever O(n log n) one.

Rough limits for about one second of running time.

Cost at a glance

Read a[i]O(1)

Halve each stepO(log n)

One passO(n)

Good sortO(n log n)

All pairsO(n²)

All subsetsO(2ⁿ)

Remember

Measure cost as the number of basic steps as a function of the input size n.
Big-O keeps only the dominant term and drops constants, so 3n² + 5n + 9 is O(n²).
With about 10⁸ steps per second, the input limits tell you which complexity you need.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the last column: 2ⁿ overtakes everything by n = 16. Try your own n values, e.g. 10 20 30 40.

Interactive visualizerfocus here, then space ← →

Growth rate race

	n	log₂n	n·log₂n	n²	2ⁿ

Big-O describes how an algorithm’s cost grows as the input n grows. Watch five growth functions race as n doubles.

Pseudocode

 1 // how does work grow with input size n? 2 compare  log n  <  n log n  <  n²  <  2ⁿ 3 O(f): ignore constants, keep the dominant term 4 // every lecture ends with an "ასიმპტოტიკა" slide

1 / 1

Check

Three questions. Pick an answer to see why.

A function runs a loop over i from 0 to n−1, and inside it a loop over j from 0 to 9. What is its complexity?

The problem says n ≤ 200 000. Which approach is likely to pass in one second?

An O(n²) program takes 1 second for n = 10 000. Roughly how long for n = 20 000?

Practice

Real problems to lock it in, easiest first.

CSESWeird Algorithm beginner↗CSESMissing Number beginner↗LeetCodeContains Duplicate beginner↗CSESTwo Knights intermediate↗