Pointer Walk

Reading Big-O from Code

Two nested loops are not always O(n²). Count the steps the inner loop really takes.

AlgorithmsBeginner9 min read

What Big-O measures

Timing code with a stopwatch tells you how fast it is on your machine, with today's data. It does not tell you what happens when the data is ten times bigger.

Big-O notation answers that question. It describes how the amount of work grows as the input grows. The input size is called n.

  • O(n): double the input, double the work.
  • O(n²): double the input, four times the work.
  • O(log n): double the input, one more step.
  • O(1): the work does not depend on the input size at all.

It deliberately ignores details. Whether a step takes 2 nanoseconds or 20 does not matter to Big-O. Only the shape of the growth does.

Count the steps

To find the Big-O of a piece of code, count how many times its innermost line runs, in terms of n.

python
for i in range(n):        # runs n times
    total += items[i]

One loop over n items: n steps. O(n).

python
for i in range(n):
    for j in range(n):    # runs n times for each i
        compare(i, j)

A loop inside a loop: n times n. O(n²).

So is the rule "two nested loops means O(n²)"?

Two nested loops that are not O(n²)

python
for i in range(n):
    j = 1
    while j < n:
        work(i, j)
        j = j * 2         # j doubles: 1, 2, 4, 8, ...

It has two nested loops. But look at how the inner one moves: j doubles each time. Starting from 1, how many doublings does it take to reach n?

Example

Counting the inner loop

For n = 8, j takes the values 1, 2, 4. Three steps.

For n = 16, j takes 1, 2, 4, 8. Four steps.

For n = 1,000,000, about 20 steps.

Doubling n adds one step. That is log₂ n.

The outer loop runs n times and the inner loop runs log n times for each, so the total is O(n log n): far closer to O(n) than to O(n²).

Here are the three shapes side by side. Run it for n = 8, then switch to 16 and 32 and watch what each bar does when n doubles.

Counting steps for n = 8Interactive
n
0
One loop
0
Inner loop doubles
0
Inner loop counts to n

Start. n = 8. All three run an outer loop 8 times. They differ in what happens inside it.

O(n)
0
O(n log n)
0
O(n²)
0

Count what the loop does, not how many loops there are. The words to watch for are how the loop variable changes: adding a constant gives n steps, multiplying or dividing gives log n steps.

The common shapes

NameBig-OWhen n doublesTypical example
ConstantO(1)No changeRead an array item by position, look up a key in a hash map
LogarithmicO(log n)One more stepBinary search
LinearO(n)DoublesScan a list once
LinearithmicO(n log n)A bit more than doublesGood sorting algorithms
QuadraticO(n²)Four timesCompare every pair
ExponentialO(2ⁿ)SquaresTry every subset

To feel the difference, here is the work for one million items:

Big-OSteps for n = 1,000,000
O(log n)20
O(n)1,000,000
O(n log n)20,000,000
O(n²)1,000,000,000,000

At a billion simple steps per second, the first three finish in a blink. The last takes about 17 minutes.

Three rules for simplifying

  1. Drop constants

    A loop that does 3 things per item is 3n steps. That is still O(n). Growth is what matters.

  2. Keep only the fastest-growing part

    n² + n is O(n²). For large n the n² part is nearly all of it.

  3. One after another: add. One inside another: multiply

    Two separate loops over n are O(n + n), which is O(n). One loop inside the other is O(n × n).

Key takeaways

  • Big-O describes how the work grows as the input grows, not how long the code takes.
  • Find it by counting how often the innermost line runs, in terms of n.
  • Nested loops are not automatically O(n²): a loop whose variable doubles runs only log n times.
  • Drop constants and smaller terms. Add for code in sequence, multiply for code that is nested.
  • Watch for single lines that hide a loop.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress