Core · AlgorithmsLesson 1 of 8Free to read

Big-O: counting steps · Data Structures and Algorithms

How do you tell whether code will still be fast with a million items?

Why you need it

Code that's instant on 10 items can take hours on 10 million. Interviewers always ask "what's the complexity?", and real systems fall over when someone picks the wrong approach. Big-O is the shorthand for how the work grows as the input grows.

The intuition

Don't time it; count the steps as n grows:

Code shape	Steps for n items	Big-O
one fixed operation	1	O(1)
one loop over the list	n	O(n)
a loop inside a loop	n × n	O(n²)
halve the problem each time	about log₂ n	O(log n)

Constants and small terms are dropped: 3n + 5 is still O(n). What matters is the shape: going from n = 1,000 to 1,000,000, O(n) work grows 1,000×, but O(n²) work grows 1,000,000×.

Definition

Time complexity

How the number of steps grows with the input size n, written in Big-O, such as O(n) or O(n²). It describes the worst case unless said otherwise.

Space complexity

How much extra memory grows with n. Using a set of seen items is O(n) space; a few variables is O(1).

Examples

Count the steps

Try it yourself

Two functions answer "is there a duplicate?". Count how many comparisons each does.

def dup_pairs(xs):
    steps = 0
    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):
            steps += 1
    return steps

def dup_set(xs):
    steps = 0
    seen = set()
    for x in xs:
        steps += 1
        seen.add(x)
    return steps

for n in [10, 100, 400]:
    data = list(range(n))
    print(n, dup_pairs(data), dup_set(data))

Step by step

L4Every pair is compared: about n × n / 2.
L11One pass: n steps.
L18At 400 items: 79800 versus 400. Four times the items, sixteen times the pairs.400 79800 400

Common mistakes

Hidden loops

x in some_list and some_list.index(x) loop over the list. Inside another loop, that's O(n²). x in some_set is O(1) on average.

Timing small inputs

On 10 items everything is fast. Reason about the shape, then test with a big input.

Quick quiz

1. A function loops over a list once, and for each item does a fixed amount of work. What's its complexity?

AO(1)
BO(n)
CO(n²)

Show the answer

Answer: B

n items × constant work = O(n).

2. What does this print?

n = 16
steps = 0
while n > 1:
    n = n // 2
    steps += 1
print(steps)

A
```
4
```
B
```
8
```
C
```
16
```

Show the answer

Answer: A

16 → 8 → 4 → 2 → 1: four halvings. That's log₂ 16.

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictCount the work
Type exactly what this program prints.
ModifyMake it O(n)
has_duplicate compares every pair, which is O(n²). Rewrite it to remember the items it has seen in a set, so it is O(n). The speed test uses 5,000 distinct numbers.
WriteBiggest gap
Write max_gap(xs) that returns the biggest difference between any two numbers in a non-empty list (largest minus smallest). One pass over the list is enough: O(n).

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Terms in this lesson

Term	Chinese	Definition
Big-O notation	大 O 记法	A description of how work grows with input size, such as O(n).
Time complexity	时间复杂度	How the number of steps grows with n.