Time complexity: counting steps in C#

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 method compares every payment with every payment after it:

static int DoublePayments(int[] ids)
{
    int found = 0;
    for (int i = 0; i < ids.Length; i++)
    {
        for (int j = i + 1; j < ids.Length; j++)
        {
            if (ids[i] == ids[j])
            {
                found++;
            }
        }
    }
    return found;
}

int[] ids = { 100231, 100232, 100233, 100232, 100234 };
Console.WriteLine("Double payments: " + DoublePayments(ids));

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:

static long steps = 0;

static int DoublePayments(int[] ids)
{
    int found = 0;
    for (int i = 0; i < ids.Length; i++)
    {
        for (int j = i + 1; j < ids.Length; j++)
        {
            steps++;
            if (ids[i] == ids[j])
            {
                found++;
            }
        }
    }
    return found;
}

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

foreach (int n in new[] { 10, 1000, 2000 })
{
    int[] ids = new int[n];
    for (int k = 0; k < n; k++)
    {
        ids[k] = 100000 + k;
    }
    steps = 0;
    DoublePayments(ids);
    Console.WriteLine($"n = {n}: {steps} steps");
}

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

static long steps = 0;

static int DoublePayments(int[] ids)
{
    int found = 0;
    for (int i = 0; i < ids.Length; i++)
    {
        for (int j = i + 1; j < ids.Length; j++)
        {
            steps++;
            if (ids[i] == ids[j])
            {
                found++;
            }
        }
    }
    return found;
}

static long steps = 0;

static int DoublePayments(int[] ids)
{
    int found = 0;
    for (int i = 0; i < ids.Length; i++)
    {
        for (int j = i + 1; j < ids.Length; j++)
        {
            steps++;
            if (ids[i] == ids[j])
            {
                found++;
            }
        }
    }
    return found;
}

static long steps = 0;

static int DoublePayments(int[] ids)
{
    var seen = new HashSet<int>();
    int found = 0;
    foreach (int id in ids)
    {
        steps++;
        if (!seen.Add(id))
        {
            found++;
        }
    }
    return found;
}

Step by step, in words

Four payments. The outer loop takes the first one, i = 0: it will be compared with every payment after it.
j walks the payments after i. Every comparison is one step, and the cell of the pair lights up: steps = 1, 2, 3.
i moves on, and j starts again from i + 1. The pairs are 3 + 2 + 1 = 6: a triangle.
Twice as many payments: 8. The steps are not 12, they are 28.
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.
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?

int full = 0;
for (int i = 0; i < 4; i++)
{
    for (int j = 0; j < 3; j++)
    {
        full++;
    }
}
int pairs = 0;
for (int i = 0; i < 4; i++)
{
    for (int j = i + 1; j < 4; j++)
    {
        pairs++;
    }
}
Console.WriteLine(full + " " + pairs);

Answer

12 6

7 4

12 16

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?

static int DoublePayments(int[] ids)
{
    int found = 0;
    for (int i = 0; i < ids.Length; i++)
    {
        for (int j = ; j < ids.Length; j++)
        {
            if (ids[i] == ids[j])
            {
                found++;
            }
        }
    }
    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.

static long steps = 0;

static int DoublePayments(int[] ids)
{
    var seen = new HashSet<int>();
    int found = 0;
    foreach (int id in ids)
    {
        steps++;
        if (!seen.Add(id))
        {
            found++;
        }
    }
    return found;
}

seen.Add(id) returns false if the number is already in the set: then the payment is a double.

foreach (int n in new[] { 10, 1000, 2000 })
{
    int[] ids = new int[n];
    for (int k = 0; k < n; k++)
    {
        ids[k] = 100000 + k;
    }
    steps = 0;
    DoublePayments(ids);
    Console.WriteLine($"n = {n}: {steps} steps");
}

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)

Algorithm	n = 10	n = 1,000	n = 2,000	n = 4,000	n = 100,000
Every pair of orders	45	499,500	1,999,000	7,998,000	≈ 4,998,750,000
The report with a set	10	1,000	2,000	4,000	100,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. .NET compiles the code to machine code (JIT). HashSet<int> keeps the numbers themselves, without wrapping, so the check is fast. The number of steps is the same as in Java, Python and JavaScript.

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):

static int[] SalesByProduct(int[] orders, int products)
{
    int[] sales = new int[products];
    for (int p = 0; p < products; p++)
    {
        foreach (int product in orders)
        {
            if (product == p)
            {
                sales[p]++;
            }
        }
    }
    return sales;
}

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

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?Seconds are too small to measureSeconds depend on the machine, the load and the language, and the number of operations depends only on the algorithm and the inputEvery operation always takes exactly one nanosecond

2. The report compares every payment with every payment after it. The payments double. How many times more steps are there?Two timesAlmost four timesAs many as before

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?Two times50 timesFour times

4. How many steps does the fix with the set make with 100,000 payments?50,000100,0004,999,950,000

Time complexity: counting steps

Cookies