Counting steps

Why not just time it?

The obvious way to compare two programs is to run both and time them. That is useful for tuning a finished program, but it is a poor way to choose an algorithm. The time depends on the machine, the language, the compiler, what else is running, and above all on the input you happened to test with. A program that is faster on 1,000 items can be hopelessly slower on a million.

What you want to know is how the work grows as the input grows. To get that, count the basic steps an algorithm takes, as a formula in terms of the input size, which is usually called n.

What counts as a step

A step is any operation that takes a fixed amount of time, whatever the size of the input: an addition, a comparison, reading or writing one array element, an assignment, a function call's overhead. On real hardware these don't cost exactly the same, as the previous module showed with cache misses, but each one is bounded by a constant, and that is enough to compare how algorithms grow.

What does not count as one step is anything that itself does work proportional to the data: searching a list, copying a list, sorting, joining strings. Those have their own step counts, which you have to add in.

Counting loops

Loops are where steps multiply, and a handful of shapes cover most code:

The trace above is the triangular case. With 4 items, the outer loop's first pass compares item 0 with the 3 items after it, the next pass compares item 1 with 2 more, then 1 more: 3 + 2 + 1 = 6 comparisons. In general that sum is n(n − 1)/2. The function compares each pair once, which is the minimum for this approach, but the number of pairs grows with the square of n.

The halving loop is the opposite extreme. Halving 1,024 reaches 1 after 10 passes, and halving a million takes only 20. That is the step count of binary search, which throws away half of the remaining items on every comparison.

From steps to seconds

A count becomes a time estimate with one rough rule: compiled code does on the order of a billion simple steps per second, and an interpreter such as Python's does tens of millions.

Apply it to the opening question. Comparing every pair of a million items is about 500 billion comparisons. That is roughly eight minutes of C and many hours of Python. The alternative, covered in the hash tables module, puts each item into a hash set and asks whether it was already there: about a million steps, which takes milliseconds even in Python. The count told you which program would finish before you wrote either of them.

Hidden loops

The hardest part of counting is noticing the loops you didn't write. Many single lines of code run a loop inside a library function:

• x in some_list and some_list.index(x) search from the start: up to n steps.
• some_list.insert(0, x) and some_list.pop(0) shift every element: n steps.
• b = a[:], list(a), sorted(a) and string slicing copy their input.
• s = s + t in a loop builds a brand-new string each time in languages with immutable strings.
• sum(a), max(a) and a.count(x) read every element.

Put one of these inside a loop over the same data and a function that looks like one loop is really two nested ones:

result = []
for x in items:            # n passes
    if x not in result:    # up to n comparisons each
        result.append(x)

This removes duplicates in up to n² steps. Using a set for result makes the membership test constant on average, and the whole function linear.

Two inputs, two variables

Not every input has one size. A function that compares every word in one document with every word in another does work proportional to the product of their lengths. If the documents have n and m words, the count is n × m, and it should stay written that way. Calling both sizes n hides the fact that a short document compared with a long one is cheap.

Grids are the most common case. A loop over every cell of a grid with r rows and c columns runs r × c times. When the grid is square that is n², but the honest count names both dimensions. The same goes for a graph, whose cost usually depends on both its number of nodes and its number of edges, as the graphs module shows.

A worked example

Here is a function with three parts. Count each one, then add them:

def summarize(a):
    total = 0
    for x in a:              # part 1: n passes
        total += x
    big = [x for x in a if x > total / len(a)]   # part 2: n passes
    for x in big:            # part 3: up to n passes...
        if big.count(x) > 1: # ...each counting through up to n items
            return True
    return False

Part 1 does n additions. Part 2 builds a list in one pass: n comparisons. Part 3 is the trap: count reads the whole list on every pass, so it does up to n × n steps. The total is n + n + n², and as the next lesson explains, only the n² part matters once n is large.

What to keep

The full formula, say n(n − 1)/2 comparisons plus n loop increments plus one return, contains more detail than you need. For a million items, the n² part is what decides whether the program finishes. The next lesson makes that precise: it keeps only the part of the count that grows fastest, which is what Big-O notation describes.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Counting steps from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

def has_duplicate(a):
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] == a[j]:
                return True
    return False

#include <vector>
#include <algorithm>
 
long long processArrayInvariants(std::vector<int>& nums) {
    long long acc = 0;
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;
    while (lo <= hi) {
        acc += nums[lo];
        if (lo < hi) acc += nums[hi];
        ++lo; --hi;
    }
    return acc;
}

public class ArrayInvariantSolver {
    public static long processArrayInvariants(int[] nums) {
        long acc = 0;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            acc += nums[lo];
            if (lo < hi) acc += nums[hi];
            lo++; hi--;
        }
        return acc;
    }
}

def process_array_invariants(nums: list[int]) -> int:
    acc = 0
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        acc += nums[lo]
        if lo < hi:
            acc += nums[hi]
        lo += 1
        hi -= 1
    return acc

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.