Big O Notation Explained With Python Examples

Big O notation describes how the running time (or memory use) of an algorithm grows as the size of its input, called n, grows. It ignores fixed costs and small details and keeps only the shape of the growth: O(1) is constant, O(log n) grows very slowly, O(n) grows in step with the input, O(n log n) is a little steeper, O(n²) grows fast, and O(2ⁿ) explodes.

Instead of stopwatch timings, which change from computer to computer, this guide counts the steps a function takes. Those numbers are the same on every machine, and every one here comes from running the code.

Why not just time the code?

A stopwatch tells you how long one run took on one computer with one input. It cannot tell you what happens when the data becomes ten times bigger, and that is exactly the question that matters. Big O answers it by counting steps as a function of n. Here are two loops, counted for three input sizes:

def count_steps_linear(n):
    steps = 0
    for i in range(n):
        steps += 1
    return steps

def count_steps_quadratic(n):
    steps = 0
    for i in range(n):
        for j in range(n):
            steps += 1
    return steps

for n in [10, 100, 1000]:
    print(n, count_steps_linear(n), count_steps_quadratic(n))

Output

10 10 100
100 100 10000
1000 1000 1000000

Multiply the input by 10 and the single loop takes 10 times as many steps: linear. The nested loop takes 100 times as many: quadratic. That difference in shape is what Big O captures.

O(1): constant time

The work does not depend on the size of the input. Reading a list item by its index, or looking a key up in a dictionary, takes about the same time whether the collection holds a thousand items or a million:

items = list(range(1_000_000))
print(items[0], items[500_000], items[-1])
d = {i: i for i in range(1000)}
print(d[999])

Output

0 500000 999999
999

(Strictly, a dictionary lookup is constant time on average. See Hash Tables in Python for why.)

O(n): linear time

The work grows in direct proportion to the input, usually because you look at every item once. A linear search through a list is the classic example. The count shows the best case (first item), the worst case (last item) and a missing value, which forces a look at everything:

def linear_search(items, target):
    steps = 0
    for i, x in enumerate(items):
        steps += 1
        if x == target:
            return i, steps
    return -1, steps

data = list(range(1, 1001))
print(linear_search(data, 1))
print(linear_search(data, 500))
print(linear_search(data, 1000))
print(linear_search(data, 5000))

Output

(0, 1)
(499, 500)
(999, 1000)
(-1, 1000)

Big O usually describes the worst case, which is 1000 steps for 1000 items. Adding up a list, printing a list, and testing x in some_list are all O(n).

O(n²): quadratic time

A loop inside a loop, both over the input, gives n × n steps. Checking a list for duplicates by comparing every pair is a typical case. The second version uses a set to remember what it has seen, and is linear:

def has_dup_slow(items):
    steps = 0
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            steps += 1
            if items[i] == items[j]:
                return True, steps
    return False, steps

def has_dup_fast(items):
    seen = set()
    steps = 0
    for x in items:
        steps += 1
        if x in seen:
            return True, steps
        seen.add(x)
    return False, steps

data = list(range(1000))
print(has_dup_slow(data))
print(has_dup_fast(data))

Output

(False, 499500)
(False, 1000)

For 1000 items with no duplicates, the pairwise method did 499,500 comparisons and the set method did 1,000 steps. At a million items, the first would need about 500 billion comparisons, while the second would still need a million. Replacing a nested loop with a set or dictionary is one of the most common speed-ups in interviews.

O(log n): logarithmic time

The work grows very slowly, because each step throws away a large fraction of the remaining input, usually half. Binary search on a sorted list is the standard example. Here we count the steps of the worst case (a value bigger than everything in the list, so it is never found) for a thousand and for a million items:

def binary_search(items, target):
    lo, hi, steps = 0, len(items) - 1, 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid, steps
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, steps

for n in [1000, 1_000_000]:
    data = list(range(n))
    print(n, binary_search(data, n)[1])

Output

1000 10
1000000 20

A thousand times more data took only twice as many steps: 10 versus 20. That is the power of O(log n). (We build binary search step by step in Binary Search in Python: 3 Common Variations.)

O(2ⁿ): exponential time

Here each extra input doubles the work. The naive recursive Fibonacci function calls itself twice per call, and the number of calls explodes:

calls = 0

def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

for n in [10, 20, 25]:
    calls = 0
    fib(n)
    print(n, calls)

Output

10 177
20 21891
25 242785

Going from 20 to 25 multiplied the calls by more than ten. By n = 50 this would take more calls than you could ever run. Yet remembering results that were already computed (memoization) collapses the whole thing to one call per value:

from functools import lru_cache

calls = 0

@lru_cache(maxsize=None)
def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

fib(25)
print(calls)

Output

26

For fib(25): 242,785 calls became 26. That is the idea behind dynamic programming.

Simplifying rules

Drop the constants

Three loops in a row, plus a few fixed steps, is still linear. Big O cares about the shape, not the multiplier:

def f(n):
    steps = 0
    for _ in range(n):
        steps += 1
    for _ in range(n):
        steps += 1
    for _ in range(n):
        steps += 1
    steps += 5
    return steps

print(f(10), f(1000))

Output

35 3005

f(n) took 3n + 5 steps, which is O(n). Ten times the input gave about ten times the steps.

Keep only the biggest term

n² + n is O(n²), because for large n the n² part dwarfs the rest. Likewise O(n + log n) is O(n).

Different inputs get different letters

If a function loops over one list of size n and, inside, another list of size m, the cost is O(n × m), not O(n²):

def pairs(a, b):
    steps = 0
    for x in a:
        for y in b:
            steps += 1
    return steps

print(pairs(range(100), range(10)))

Output

1000

Loops one after another add (O(n + m)). Loops inside each other multiply (O(n × m)).

Hidden costs

Some innocent-looking Python operations hide a loop. Watch for these:

• x in some_list is O(n). On a set or dict it is O(1) on average.
• Slicing, items[1:], copies the elements, so it is O(n).
• list.insert(0, x) and list.pop(0) shift every element, so they are O(n).
• Building a string with += in a loop can be O(n²) overall.
• sorted() and list.sort() are O(n log n).

Slicing in a loop is a subtle trap. This function adds up a list by repeatedly chopping off the first item, and counts how many elements the slices copied:

def sum_slices(items):
    copied = 0
    total = 0
    while items:
        total += items[0]
        items = items[1:]
        copied += len(items)
    return total, copied

print(sum_slices(list(range(1, 101))))

Output

(5050, 4950)

Adding up 100 numbers copied 4,950 elements along the way: O(n²) work for a job a simple loop does in O(n). The full table for Python’s built-in types is in Time Complexity of Python Data Structures.

The growth rates side by side

Read across the last row: for a thousand items, O(n) is a thousand steps, O(n²) is a million, and O(2ⁿ) is a number with 302 digits. This is why the choice of algorithm matters far more than the speed of the computer.

Space complexity

Big O also describes memory. A function that builds a new list of n items uses O(n) extra space. One that only keeps a few counters uses O(1). Generators (see Python Iterators and Generators Explained) are a way to turn O(n) memory into O(1). Time and space often trade off: the set in the duplicate check made the code faster by using extra memory.

Common mistakes

• Thinking Big O is exact time. It describes growth. An O(n) algorithm with a big constant can lose to an O(n²) one on tiny inputs.
• Assuming nested loops are always n². If the inner loop runs a fixed number of times, or over a different-sized input, the cost is different.
• Forgetting hidden loops. A slice, an in on a list, or a sum() inside a loop adds a factor of n.
• Mixing up best, average and worst case. Quote the worst case unless told otherwise.
• Ignoring space. A fast solution that needs a huge amount of memory may not be a good one.

Try it yourself

Work out each answer first, then open the solution.

1. A function loops over a list of n items twice, one loop after the other. What is its Big O?

2. How many steps does this take, and what is the Big O?

print(sum(1 for i in range(50) for j in range(50)))

2500

3. This loop halves n each time. How many steps for n = 1000, and what is the Big O?

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

9

4. You must check whether a value is present in a collection of a million items, many times over. Should you keep them in a list or a set?

Run the counters in our free Python compiler and try other sizes.

Frequently asked questions

What is Big O notation in simple words?

It is a way of describing how much longer (or how much more memory) an algorithm needs as its input gets bigger. It focuses on the shape of the growth, such as constant, linear or quadratic, instead of exact times.

Why do we ignore constants in Big O?

Because for large inputs the shape of the growth dominates. An algorithm that takes 3n steps and one that takes n steps both grow linearly, so both are O(n).

What does O(log n) mean?

The number of steps grows very slowly, because each step removes a big share of the remaining work, typically half. Binary search takes about 20 steps for a million items.

Is O(n) always faster than O(n²)?

For large inputs, yes. For very small inputs the constants can matter more, so a simple quadratic method can win. Big O tells you what happens as data grows.

What is the difference between time complexity and space complexity?

Time complexity describes how the running time grows with the input. Space complexity describes how the extra memory used grows.

What is amortized O(1)?

An operation that is occasionally expensive but cheap on average over many calls. list.append() is the standard example: it sometimes has to resize the list, but averaged over many appends it is constant time.

Related reading

• Time Complexity of Python Data Structures – the cost of list, dict and set operations.
• Binary Search in Python: 3 Common Variations – O(log n) in practice.
• Hash Tables in Python: Dict and Set for DSA – why lookups are O(1).
• How to Learn DSA in Python: A Roadmap – where Big O fits.