Counting steps and choosing a Python interpreter¶

~15 min · prerequisite: A fast input and output template

What you will be able to do¶

Count how many loop iterations a piece of code runs, and write that count as a formula.
Decide whether a loop over the input size fits a time limit, using a measured speed as a guide.
Explain what PyPy is and why a judge might offer it.

The idea¶

A judge gives each test a time limit, often one or two seconds. Your program must finish inside it. You cannot run every idea on the judge to see, so you estimate the work first. The estimate counts steps, which means how many times the core part of a loop runs.

The tool for this is Big-O notation. Big-O describes how the number of steps grows as the input size n grows, and it ignores constant factors and small terms. Counting steps by hand gives the formula, and Big-O keeps only its dominant part.

A single loop over n items runs n times, so its cost is O(n). A loop inside another loop, where both run up to n times, runs n × n times, so its cost is O(n²). If the inner loop starts at the outer index, the work shrinks. For i from 0 to n - 1, the inner loop runs n - 1 - i times. Adding these gives (n - 1) + (n - 2) + ... + 0 = n(n - 1) / 2, which is still O(n²).

Some steps are built into Python and cost more than one loop iteration. Sorting a list of n items is done by Timsort, a method built on merging sorted pieces. Each merge round halves the number of pieces, so there are about log2(n) rounds, and each round compares about n pairs of items. That gives roughly n log2(n) work.

To turn counts into a decision, you need a speed. Measure one on your own machine. On the machine used to check this lesson, a loop that adds 10 million integers took about 2 seconds, and a nested loop with 100 million inner steps took about 27 seconds. Judges differ, so treat these as rough guides. For n = 200000, an O(n²) method needs 4 × 10^10 steps and is far too slow. An O(n log n) method needs about 200000 × 18 = 3.6 × 10^6 steps and fits comfortably.

PyPy is a different implementation of the Python language. It can run long plain loops much faster than the standard interpreter, which is called CPython. It does not speed up everything equally, it has a different start-up cost, and some libraries written in C are not available. Some judges offer it as a separate language. Time your code under both before you choose.

Worked example¶

This function counts pairs of equal values with two nested loops, and it also counts how many times the inner comparison runs.

def count_equal_pairs_slow(values):
    comparisons = 0
    pairs = 0
    n = len(values)
    for i in range(n):
        for j in range(i + 1, n):
            comparisons += 1
            if values[i] == values[j]:
                pairs += 1
    return pairs, comparisons


pairs, comparisons = count_equal_pairs_slow([1, 2, 1, 3, 1])
assert pairs == 3
assert comparisons == 10

Line by line, this is what Python does:

The function sets two counters to zero. n holds the length of the list.
The outer loop runs i from 0 to n - 1.
The inner loop starts at i + 1, so each pair (i, j) with i < j is visited exactly once.
Each visit adds one to comparisons, then compares two values.
For n = 5, the inner loop runs 4 + 3 + 2 + 1 + 0 = 10 times. The assertion checks this formula against the count.
The three equal pairs are the positions of the three 1 values: (0, 2), (0, 4) and (2, 4).

The formula n(n - 1) / 2 is an exact count, not only an estimate, so you can check it with assert.

Try it¶

The first block checks the formula for many sizes. The second block shows a faster method that avoids the inner loop.

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


for n in range(0, 50):
    assert count_steps(n) == n * (n - 1) // 2

from collections import Counter


def count_equal_pairs_fast(values):
    total = 0
    for c in Counter(values).values():
        total += c * (c - 1) // 2
    return total


assert count_equal_pairs_fast([1, 2, 1, 3, 1]) == 3
assert count_equal_pairs_fast([]) == 0

Common mistakes¶

Using a nested loop over the full input. No error appears when the code is written. The judge reports the verdict Time limit exceeded on large tests. Count the steps before you write the loops.
Searching a list inside a loop. The test x in some_list scans the list from the start until it finds x. Inside a loop over n items it costs about n² steps overall. Build a set once and test membership in it.
Recursing too deep. Python limits the depth of nested function calls. The default limit is 1000, and this code fails:
```
def depth(n):
    return depth(n + 1)


depth(0)
```
```
RecursionError: maximum recursion depth exceeded
```
Replace deep recursion with a loop, or rewrite the function so its depth stays small.
Timing once and trusting the number. A single run can be affected by other programs on the machine. Repeat the timing, or measure with time.perf_counter, and compare the same code under both interpreters.

Practice¶

For n = 6, the loop for i in range(n): for j in range(i): ... runs the inner body how many times? Check with assert.
How many values does range(1, 10, 2) produce? Check the count with len.
Medium: write harmonic_steps(n) that counts the steps of for i in range(1, n + 1): for j in range(i, n + 1, i): .... Check that harmonic_steps(10) equals 27.
Medium: for n = 2 * 10**5, use math.log2 to estimate n * log2(n), and assert it is below 10**7.
Stretch: check with itertools.combinations that the number of triples i < j < k from six items is 6 * 5 * 4 // 6.

Solution

python count = 0 for i in range(6): for j in range(i): count += 1 assert count == 15
python assert len(range(1, 10, 2)) == 5
```python def harmonic_steps(n): steps = 0 for i in range(1, n + 1): for j in range(i, n + 1, i): steps += 1 return steps

assert harmonic_steps(10) == 27 ```

The multiples of i up to n are i, 2i, ..., so the inner loop runs n // i times. The total is n // 1 + n // 2 + ... + n // n, which grows like n ln n.

```python import math

estimate = 2 * 105 * math.log2(2 * 105) assert estimate < 10**7 ```

```python import itertools

assert len(list(itertools.combinations(range(6), 3))) == 6 * 5 * 4 // 6 ```

Recap¶

Count steps with a formula first, then use Big-O to compare how the count grows with n.
Measure your interpreter's speed once, and use it to decide whether a step count fits the time limit.
PyPy can help with long loops, but time your own code before choosing it, and avoid deep recursion.