Time and Space Complexity

Start with a real problem. Say you run a website, and you keep a log of every sign-up, one user name per line. Some people sign up more than once, so the same name can appear in the log several times. You want a list of the names with each one kept once, in the order they first signed up.

Making a sign-up log

There is no real log here, so you will make one. make_signups builds a list of n user names, picked at random with the random module. It uses a seed of zero, so your names match the ones below:

import random

def make_signups(n, seed=0):
    r = random.Random(seed)
    return [f"user{r.randrange(n)}" for _ in range(n)]
signups = make_signups(1_000)
signups[:5]

['user864', 'user394', 'user776', 'user911', 'user430']

The first five of the thousand names are user864, user394, user776, user911 and user430.

unique

Here is a function that does the job, and it is the kind of loop you have written many times. unique starts with an empty list called seen. Then, for each name, if the name is not in seen yet, it appends it. So the first time a name comes up, it is kept, and every time after that, it is skipped:

def unique(names):
    seen = []
    for name in names:
        if name not in seen:
            seen.append(name)
    return seen
len(unique(signups))

620

On the thousand sign-ups, it keeps 620 names.

Timing it

Now time it. The timeit module in Python's standard library runs a piece of code and reports how many seconds it took. Here, timeit.timeit calls unique(values) ten times, and dividing by ten gives the seconds for one call:

import timeit

values = make_signups(1_000)
elapsed = timeit.timeit(
    lambda: unique(values),
    number=10
) / 10
elapsed

0.004308130699791945

Now scale that up to ten thousand sign-ups:

values = make_signups(10_000)
elapsed = timeit.timeit(
    lambda: unique(values),
    number=10
) / 10
elapsed

0.5074694916002045

These are the times from one run on one machine. Your own times will be different, because seconds change from one machine to the next and from one run to the next. What matters is the shape: ten times the sign-ups took roughly a hundred times as long.

Why the time grows faster than the data

So why does the time grow so much faster than the data? And can you work out how it grows without waiting for a million sign-ups? That is what time complexity is for, and it is what this lesson is about. Programmers use it for every kind of program, from a website to a database. And when you study machine learning, you will use it to measure how long a model takes to train, and to predict.

Leave the sign-ups for a moment, and start with the smallest example there is: finding the largest value in a list. largest starts with best as the first value. Then it goes through the list, and whenever a value is bigger than best, that value becomes the new best.

There is one more thing in it: a variable called comparisons, which goes up by one every time the loop compares a value with best. It is only there so you can see how much work the function does:

def largest(values):
    best = values[0]
    comparisons = 0
    for value in values:
        comparisons += 1
        if value > best:
            best = value
    return best, comparisons
largest([3, 26, 54, 3, 1, 22, 56, 32, 31])

(56, 9)

On the list 3, 26, 54, 3, 1, 22, 56, 32 and 31, it gives 56. And for those nine values, it made nine comparisons.

How the count grows

So what happens to the count as the list grows? Run largest on lists of 10, 100 and 1,000 values, and keep only the count:

[largest(list(range(n)))[1] for n in (10, 100, 1_000)]

[10, 100, 1000]

For ten values, largest makes ten comparisons. For a hundred, it makes a hundred, and for a thousand, it makes a thousand. So the count grows exactly as fast as the list does.

Count operations, not seconds

That is why you count operations, and not seconds. A comparison takes about the same time every time it runs, so counting comparisons shows you how the time grows. Seconds change from one machine to the next, and from one run to the next, but the count does not.

And that is what time complexityKey termHow the number of operations grows with the size of the input. is: how the number of operations a function makes grows with the size of its input.

But not every function makes the same number of comparisons each time. Here is one that checks whether a user id is taken. contains goes through the values, comparing each one with the target, and returns True as soon as it finds a match, along with the number of comparisons it made. If it gets to the end without a match, it returns False.

Use the same nine values as user ids:

def contains(values, target):
    comparisons = 0
    for value in values:
        comparisons += 1
        if value == target:
            return True, comparisons
    return False, comparisons
ids = [3, 26, 54, 3, 1, 22, 56, 32, 31]
contains(ids, 32)

(True, 8)

For 32, contains gives True after eight comparisons, because 32 is the eighth value in the list. Now try 3, the first value:

contains(ids, 3)

(True, 1)

It is found after one comparison. And 31, the last value, takes nine:

contains(ids, 31)

(True, 9)

The best and worst case

So the same function can take one comparison, or it can take nine, and it all depends on what you search for. The fewest operations a function can make for an input of a given size is its best caseKey termThe fewest operations any input of size n needs: a linear search that finds its value first time makes one comparison., and the most is its worst caseKey termThe most operations any input of size n needs: a linear search for an absent value compares with all n. Complexity is quoted for the worst case unless it says otherwise.. For contains on these nine values, one is the best case and nine is the worst case.

The average case

The average caseKey termThe expected operation count under a stated distribution of inputs. For n distinct values with equally likely successful targets, linear search averages (n + 1) / 2 comparisons. Duplicates or unequal target probabilities change this mean. is the average number of operations, and it depends on how likely each target is. Say you pick each of the nine entries as the target once, and average the counts:

round(sum(contains(ids, target)[1] for target in ids) / len(ids), 2)

4.67

Notice that 3 comes up twice in the list, and both of those searches stop at its first position, after one comparison. So the average is about 4.67 comparisons.

Which case people mean

When people give the time complexity of a function, they mean the worst case, unless they say otherwise, because that is the number you can rely on. And a search like this one, going through the values one at a time from the start, is called a linear searchKey termChecking the values one at a time from the start: O(n)..

So far

Before getting to Big-O, here is what you have so far. You count one kind of operation, like a comparison, not seconds, and you look at how that count grows as the input grows. And when you say how a function grows, you mean its worst case.

Now, contains does a bit more than compare. It adds one to comparisons, and it goes round the loop. So if you counted every line it runs, you would get something like four times n, plus four, where n is the number of values. People write that as 4n + 4.

But look at what happens as n grows. Here is 4n + 4 for a thousand, ten thousand and a hundred thousand values:

[4 * n + 4 for n in (1_000, 10_000, 100_000)]

[4004, 40004, 400004]

The totals are 4,004, then 40,004, then 400,004. Each time n gets ten times bigger, so does the total, just like n on its own.

Dropping the constants

So for how a function grows, the four in front of n and the plus four do not matter. You drop those constants, and say that contains is "O of n", written O(n).

That is called Big-O notationKey termAn asymptotic upper bound on growth. These lessons use the tightest usual bound, dropping constants and smaller terms: 4n + 4 is O(n)., and it gives an upper bound on how the work grows as the input grows. O(n) is the tightest such bound for this linear scan, and it is also called linear timeKey termO(n): ten times the input, ten times the operations.: the work grows in step with the input.

Keeping the largest term

When there is more than one term, you keep only the largest. Say a function takes three times n squared, plus two times n, plus four operations. "n squared" means n times n, and people write it n², so this total is 3n² + 2n + 4. Work out the two parts at n equals a thousand:

n = 1_000
3 * n**2, 2 * n + 4

(3000000, 2004)

Three n squared is three million, and two n plus four is 2,004. So the two n plus four is less than a tenth of one percent of the total, and it gets smaller still as n grows. That function is "O of n squared", written O(n²), which is called quadratic timeKey termO(n²): doubling the input quadruples the operations, as comparing every pair does..

Constant time

And a function that takes the same number of operations whatever n is, like reading the value at index zero with values[0], or calling len(values), is "O of one", written O(1). That is called constant timeKey termO(1): the same number of operations however large the input, such as values[0] or len(values)..

The five you will meet

There are five of these you will meet all the time: O(1), O(log n), O(n), O(n log n) and O(n²). Here, log n is the base-two logarithm: the number of times you can halve n before you reach one. To see how far apart the five are, put numbers on them for n equal to a thousand:

import math
[1, round(math.log2(n)), n, round(n * math.log2(n)), n**2]

[1, 10, 1000, 9966, 1000000]

When n is a thousand, they are 1, about 10, 1,000, about 10,000, and a million. That is a factor of a million between the first and the last, for the same thousand values. The next two lessons are about moving a program from the right-hand end of that list towards the left.

So what does an O(n²) function look like? Here is one that checks whether a list has a duplicate in it. has_duplicate takes every value in turn, and compares it with every value after it. That is two loops, one inside the other:

def has_duplicate(values):
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] == values[j]:
                return True
    return False
has_duplicate([3, 26, 54, 3]), has_duplicate(list(range(1_000)))

(True, False)

On 3, 26, 54 and 3, it gives True. On the numbers from 0 to 999, which are all different, it gives False.

Counting the pairs

So how many comparisons does it make, for a thousand values with no duplicate? The first value is compared with the 999 after it, the second with 998, and so on, down to none for the last. Add those up, and compare the total with the formula n times (n minus one), divided by two:

sum(len(range(i + 1, n)) for i in range(n)), n * (n - 1) // 2

(499500, 499500)

Both give 499,500. That is n times (n minus one), divided by two, which is about n squared over two. Drop the constant one half, and has_duplicate is O(n²).

Doubling the list

The same question in O(n)

You can answer the same question in O(n). A set keeps each value once, so if the set of the values is shorter than the list, there was a duplicate:

def has_duplicate_fast(values):
    return len(set(values)) < len(values)
has_duplicate_fast([3, 26, 54, 3]), has_duplicate_fast(list(range(1_000)))

(True, False)

Building the set goes through the values once, so doubling n roughly doubles the work, just as O(n) should.

Now go back to the sign-ups, because unique has only one loop. So why did it grow like has_duplicate, and not like largest?

The answer is that Python's own operations have a time complexity too. Checking whether a value is in a list is O(n), because it is a linear search, the same as your contains. But checking whether a value is in a set is O(1) on average, because of the hashing you saw in the sets lesson.

Operations you use all the time

There are a few more you will use all the time:

• Indexing and len are O(1), and so is append, on average. Now and then, append has to resize the list and copy its references, so people say it is O(1) amortized: averaged over many appends, each one costs a constant amount.
• Anything that has to go through every value, like max or sum, is O(n). So is inserting at the front with insert(0, ...), because every item after it has to move up one place.
• sorted is O(n log n).

The hidden loop

So look at unique again:

def unique(names):
    seen = []
    for name in names:
        if name not in seen:
            seen.append(name)
    return seen

The fix

The fix is small. You make seen a set instead, and keep the names you are keeping in a list of their own, so their order stays the same:

def unique_fast(names):
    seen = set()
    kept = []
    for name in names:
        if name not in seen:
            seen.add(name)
            kept.append(name)
    return kept
unique_fast(signups) == unique(signups)

True

unique_fast gives exactly the same list as unique, in the same order. It does for ten thousand sign-ups too:

bigger = make_signups(10_000)
unique_fast(bigger) == unique(bigger)

True

And on a hundred thousand sign-ups, it keeps the same number of names:

len(unique_fast(make_signups(100_000)))

63149

Now time it on those hundred thousand sign-ups, with the same timeit code as before:

values = make_signups(100_000)
elapsed = timeit.timeit(
    lambda: unique_fast(values),
    number=10
) / 10
elapsed

0.011120057700100005

In this run, that is about 11 milliseconds per call, where unique took about 54 seconds on the same machine.

Inserting at the front

Here is the same idea with insert. The code below times inserting one value at the front of a list, and then removing it again with pop(0), so the list stays the same length for every repeat. Next to it, it times append followed by pop(), which adds and removes at the end. Both are repeated ten thousand times, and dividing gives the seconds for one repeat:

values = list(range(10_000))
front = timeit.timeit("values.insert(0, 1); values.pop(0)", globals=globals(), number=10_000) / 10_000
end = timeit.timeit("values.append(1); values.pop()", globals=globals(), number=10_000) / 10_000
front, end

(3.800803999911295e-06, 4.451210006664042e-08)

Now do the same on a list ten times longer:

values = list(range(100_000))
front = timeit.timeit("values.insert(0, 1); values.pop(0)", globals=globals(), number=10_000) / 10_000
end = timeit.timeit("values.append(1); values.pop()", globals=globals(), number=10_000) / 10_000
front, end

(4.115299910008616e-05, 4.423139980644919e-08)

Again, these are one run on one machine. The shape is what to look for: ten times the list took about ten times as long at the front, so inserting at the front is O(n). At the end, the time stayed about the same at both sizes, well under a tenth of a microsecond. So when you need to add values one at a time, add them at the end.

So far, you have counted time. But a function also uses memory, and how much extra memory it needs as its input grows is called its space complexityKey termHow memory use grows with input size. Extra storage excludes the input; auxiliary space also excludes the returned output. State which is being counted.. You do not count the input itself, only what the function adds.

So largest keeps one value, best, however long the list is, and that is O(1) space. sorted builds a new list with every value in it, so it is O(n) space. And unique_fast keeps a set of every name it has seen, so it is O(n) space as well.

Measuring bytes with getsizeof

You can measure memory in bytes, too. sys.getsizeof gives the size of an object in bytes:

import sys
sys.getsizeof([]), sys.getsizeof(list(range(1_000))), sys.getsizeof(list(range(1_000_000)))

(56, 8056, 8000056)

On 64-bit CPython, the standard Python on most computers, an empty list is 56 bytes. That is the list itself, because getsizeof does not include the objects it refers to. A list of a thousand numbers is 8,056 bytes, and a list of a million is 8,000,056.

That is 8,000 extra bytes for a thousand values:

(8056 - 56) / 1_000

8.0

Eight bytes per value, which is the reference the list stores for each value. The list grows in proportion to n, so it takes O(n) space.

A trade-off

And that is the choice both of your fast versions made. Not counting the result they return, has_duplicate_fast and unique_fast each use O(n) extra space for their set, where the slow versions use O(1). In return, they went from O(n²) time to O(n).

Using more memory to save time, or more time to save memory, is called a trade-offKey termUsing more of one resource, memory or time, to use less of the other: a set spends O(m) memory to make each check O(1).. On a laptop, a set of a hundred thousand names is small. But on a device with very little memory, the slow version can be the right choice.

Big-O describes growth, not speed

One more thing about Big-O. It describes how a function grows, not how fast it is. For a small input, like ten values, the constants that Big-O drops can determine which version is faster. So when the input is small, time both versions, rather than choosing one from its Big-O.

You started with unique slowing down sharply on a hundred thousand sign-ups, where ten times the data took about a hundred times as long, and time complexity explains that. It is how a function's number of operations grows with the size of its input, and you give the worst case. Big-O notation drops the constants and keeps only the largest term, and the five you will meet most are O(1), O(log n), O(n), O(n log n) and O(n²).

A loop inside a loop is often O(n²), and that is what unique was, because one line, checking whether a name is in a list, was a loop of its own. Switching to a set made it O(n), using O(n) extra memory, and that extra memory is what space complexity measures.

Your challenge

Take count_words from the module on organizing code, which counts how often each token appears, using a dictionary:

def count_words(tokens):
    counts = {}
    for token in tokens:
        counts[token] = counts.get(token, 0) + 1
    return counts
tokens = ["great", "kettle", "boils", "fast", "great"] * 2_000
len(tokens), len(count_words(tokens))

(10000, 4)

Write down its time complexity and its space complexity. Then check your answer by timing it on ten thousand tokens and on twenty thousand.

Your sign-up log is in the order people signed up, so it is sorted by time. Say you want to find where one day starts, in a log of a million entries. A linear search would check the entries one at a time, from the start. But when the entries are sorted, do you really need to check every one? In the next lesson, you will see how to find a value in a sorted list by checking only about twenty of a million values.