Counting Steps: O(1), O(n), O(n²)

Counting steps

In lesson 1-1 the list did 10,000 checks and the dict did 1. We need a language for that difference, one that does not depend on how fast your laptop is. That language is Big-O notation.

The idea: instead of measuring seconds, count the steps a piece of code takes as a function of the input size, which we call n. Then keep only the part that grows.

• Reading names[500] is one step no matter how long the list is. We write O(1), constant time.
• Scanning a list of n items is about n steps: O(n), linear time.
• Comparing every item to every other item is n × n steps: O(n²), quadratic time.

Let's count for real.

Counting one loop against two

count_linear walks a single loop, and count_pairs nests one loop inside another. The interesting part is what each count does when n grows tenfold.

def count_linear(n):
    steps = 0
    for _ in range(n):
        steps += 1
    return steps

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

for n in [10, 100, 1000]:
    print(n, count_linear(n), count_pairs(n))

Output

10 10 100
100 100 10000
1000 1000 1000000

The linear count grows exactly as fast as n does: ten times the input, ten times the steps. The pairs count grows a hundredfold for the same tenfold input, because each of the n outer passes triggers all n inner passes.

That is the whole difference between O(n) and O(n²) made visible, and it is a difference in rate rather than in size. At n = 10 the gap is 90 steps and easy to ignore. At n = 1000 it is nearly a million.

Dropping the noise

Big-O keeps only the fastest-growing term and ignores constant factors, because for large n nothing else affects the outcome.

• 3n + 12 steps becomes O(n). Both the 3 and the 12 disappear.
• n²⁄2 + n steps becomes O(n²). Half of a quadratic is still a quadratic.
• 5 steps, always, is O(1).

Being this ruthless looks careless until you put numbers on it. At n = 1,000,000 an O(n) pass is a million steps and an O(n²) pass is a trillion. A computer managing 100 million steps per second finishes the first in about 0.01 seconds and the second in roughly 3 hours.

Constant factors move that result by a factor of 2 or 3. The growth family moves it by hours. Big-O throws away the small effect so it can talk clearly about the large one.

A function doing 2n + 10 steps is O(n).

Big-O drops the constant multiplier, the 2, and the lower-order term, the +10, keeping only the growth family. What remains grows linearly with n.

Writing O(2n + 10) is simply not done, and the reason is worth stating: the notation exists to hide exactly those details. Two implementations at 2n + 10 and 40n + 3 steps are both O(n), which is Big-O asserting they belong in the same category, and any real choice between them comes from measurement rather than from notation.

A nested loop that runs half as often

This version's inner loop runs i times rather than n times, so the passes form a triangle rather than a square.

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

for n in [10, 100, 1000]:
    print(n, triangle_steps(n))

Output

10 45
100 4950
1000 499500

Because the inner loop is for j in range(i), the first pass with i = 0 runs zero times, the second runs once, and so on. The totals are therefore 0 + 1 + 2 + ... + (n−1), which equals n(n−1)⁄2.

For n = 1000 that is 499,500, close to half a million where the full square version reached a full million. Genuinely half the work.

And yet the growth pattern is unchanged. Going from n = 100 to n = 1000 multiplied the count by roughly 100, exactly as the square version did, which is the fact the next block turns into a rule.

The triangle loop is still O(n²) because ½ is a constant factor and Big-O keeps only the growth family.

Expanding it makes this concrete. n(n−1)⁄2 = n²⁄2 − n⁄2, and dropping the lower-order n⁄2 along with the constant ½ leaves n².

The behavior confirms it. When n doubles, the work roughly quadruples in the triangle version exactly as in the square version, and that quadrupling is precisely what O(n²) names. Halving the total does not change how the total responds to a bigger input, which is the only thing Big-O measures.