Skip to content
wannacode

Time complexity: counting steps

In short: Time complexity says how the number of basic operations grows with the size of the input: a nested loop makes n(n − 1) / 2 steps, one pass with a set makes n.

Problem

The report that never finishes

Every month the online shop runs a sales report. One of its checks looks for double payments: the same payment charged twice because someone pressed the button again. The function compares every payment with every payment after it:

def double_payments(ids):
    found = 0
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            if ids[i] == ids[j]:
                found += 1
    return found
ids = [100231, 100232, 100233, 100232, 100234]
print("Double payments: " + str(double_payments(ids)))
Output
Double payments: 1

A year ago there were 1,000 orders a month and the report was ready in 2 seconds. Today there are 100,000. The report starts in the evening and it is still running in the morning. Nobody touched the code. The data is 100 times bigger, and the time is not 100 times longer, it is much longer.

Why? And how could you know in advance, without waiting all night?

The idea

Seconds lie, steps do not

How many seconds a program takes depends on many things outside it:

  • the machine: the laptop and the server give different numbers;
  • the load: the same report is slower while the server is also serving customers;
  • the language: the same calculation is several times slower in Python than in Java or C#.

So we measure something else: how many times the program does its basic operation. Here that is one comparison of two numbers. Their count depends neither on the machine nor on the language, only on the algorithm and the input. This is called the number of operations (or the number of steps).

The number of operations does not tell you the seconds. It tells you something more useful: how many times more work comes when the data grows.

See it

Counting the steps

You put a counter next to the comparison. Every comparison is one step:

steps = 0




def double_payments(ids):
    global steps
    found = 0
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            steps += 1
            if ids[i] == ids[j]:
                found += 1
    return found

The report runs on 10, 1,000 and 2,000 payments with different numbers:

for n in [10, 1000, 2000]:
    ids = [100000 + k for k in range(n)]
    steps = 0
    double_payments(ids)
    print(f"n = {n}: {steps} steps")
Output
n = 10: 45 steps
n = 1000: 499500 steps
n = 2000: 1999000 steps

The first payment is compared with n − 1 others, the second with n − 2, and so on until the last one, which has nobody left. The sum is

n(n − 1) / 2

With 1,000 payments that is 499,500 steps. With 100,000 it is 4,999,950,000: 10,010 times more for 100 times more data. If the two seconds went almost entirely to the comparisons, now they go to more than five and a half hours. The answer was in the code a year ago: you only had to count.

See it

Why almost ×4

steps = 0




def double_payments(ids):
    global steps
    found = 0
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            steps += 1
            if ids[i] == ids[j]:
                found += 1
    return found
Step by step, in words
  1. Four payments. The outer loop takes the first one, i = 0: it will be compared with every payment after it.
  2. j walks the payments after i. Every comparison is one step, and the cell of the pair lights up: steps = 1, 2, 3.
  3. i moves on, and j starts again from i + 1. The pairs are 3 + 2 + 1 = 6: a triangle.
  4. Twice as many payments: 8. The steps are not 12, they are 28.
  5. 28 = 6 old pairs + 6 pairs of the new ones + 16 pairs of a new one with an old one. Almost ×4: with 1,000 → 2,000 payments it is 499,500 → 1,999,000 steps.
  6. The fix walks the payments once and remembers them in seen: 8 payments, 8 steps. Twice as many payments here means twice as many steps.

Doubling is not just "as many payments again". The old 6 pairs stay. 6 pairs come among the new payments. And 16 more: each of the 4 new ones with each of the 4 old ones. 28 in total. The "new with old" part is a square, and it grows the fastest. That is why for a large n doubling gives almost exactly ×4.

More precisely, if you are curious

The arithmetic for every n: with 2n payments the pairs are 2n(2n − 1) / 2 = 4 · n(n − 1) / 2 + n. That is four times the old pairs and n more. With n = 4 that is 4 · 6 + 4 = 28, and with n = 1,000 it is 4 · 499,500 + 1,000 = 1,999,000. The extra n is small next to the rest, and the bigger n is, the smaller it gets.

Try it

Predict the output

Two nested loops. The first goes over 4 warehouses and for each one over 3 delivery hours. The second goes over every pair of the 4 warehouses. What does the program print?

full = 0
for i in range(4):
    for j in range(3):
        full += 1
pairs = 0
for i in range(4):
    for j in range(i + 1, 4):
        pairs += 1
print(full, pairs)
Answer

Try it

Fill in

The report has to compare every pair exactly once and never compare a payment with itself. Where does the inner loop start?

def double_payments(ids):
    found = 0
    for i in range(len(ids)):
        for j in range(, len(ids)):
            if ids[i] == ids[j]:
                found += 1
    return found

See it

The fix: one pass

There is no need to compare every payment with every other one. It is enough to remember the numbers you have already seen. A set keeps those numbers and tells you whether a number is in it, without walking through them one by one.

steps = 0




def double_payments(ids):
    global steps
    seen = set()
    found = 0
    for payment in ids:
        steps += 1
        if payment in seen:
            found += 1
        else:
            seen.add(payment)
    return found
payment in seen asks the set whether the number is in it. The name is not id, because id is a built-in function in Python.
for n in [10, 1000, 2000]:
    ids = [100000 + k for k in range(n)]
    steps = 0
    double_payments(ids)
    print(f"n = {n}: {steps} steps")
Output
n = 10: 10 steps
n = 1000: 1000 steps
n = 2000: 2000 steps

The steps are as many as the payments. Twice as many payments means twice as many steps. Run the two reports side by side:

  • Every pair of orders O(n²)
  • The report with a set O(n)
Algorithmn = 10n = 1,000n = 2,000n = 4,000n = 100,000
Every pair of orders45499,5001,999,0007,998,000≈ 4,998,750,000
The report with a set101,0002,0004,000100,000
The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.
More precisely, if you are curious

Which operation is the basic one? The one that repeats the most and that the time depends on. In the slow report that is the comparison in the inner loop. Incrementing i and j and checking whether the loop is over also repeat, but as many times as the comparisons, not more. So their count does not change the picture and is not counted separately.

Is the check in the set one step? Not quite: behind the set there is a hash table, which computes the hash of the number and looks into one bucket. On average this is the same small amount of work, however many numbers there are inside. You will see how in the module "Data structures". Here we count it as one step, just as Bench does.

Seconds in the different languages. The number of steps is the same, and the time is not. Python runs every step of the loop through the interpreter and is tens of times slower per step than Java and C#. The 1,999,000 steps here take about a tenth of a second, in Java a few milliseconds. If the report has to be fast, you change the algorithm first and only then the language.

Exercise

Sales by product

Solve the task in your editor.

How many steps. The sales report counts how many times each of the 50 products was ordered. An order is the number of the product (from 0 to 49):

def sales_by_product(orders, products):
    sales = [0] * products
    for p in range(products):
        for product in orders:
            if product == p:
                sales[p] += 1
    return sales

Add a counter steps before the comparison. Run the function with 1,000 and with 2,000 orders, where the product of order k is k % 50, and print the steps:

Output
n = 1000: 50000 steps
n = 2000: 100000 steps

The loop is nested, and yet the steps only double. Why?

More tasks

  • One pass. Write the sales report with one pass over the orders: sales[product] grows by one for every order. How many steps are there with 1,000 orders?
  • The report of the year. How many steps does the slow double payment report make for a whole year with 100,000 payments a month? Work it out with n(n − 1) / 2, without running it.
  • Your code. Find a nested loop in your own code and count its steps for two input sizes. What happens when the input doubles?

Test

Check yourself

1. Why do we count operations and not seconds?
2. The report compares every payment with every payment after it. The payments double. How many times more steps are there?
3. The sales report goes through all 50 products, and for every product it goes through all orders. The orders double. How many times more steps are there?
4. How many steps does the fix with the set make with 100,000 payments?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·