Complexity is how the work grows when the input grows. Count comparisons. A loop over n items is about n steps. A nested loop is about n².

Goal

Count steps for a scan and for every-pair work, and print both.

Linear in n

def count_scan(xs, target):
    steps = 0
    for x in xs:
        steps += 1
        if x == target:
            return steps
    return steps

cities = ["Nairobi", "Mombasa", "Kisumu", "Nakuru", "Eldoret"]
print("find Kisumu", count_scan(cities, "Kisumu"))
print("miss Eldama", count_scan(cities, "Eldama"))

A miss walks the whole list: n comparisons.

Quadratic in n

def count_pairs(xs):
    steps = 0
    n = len(xs)
    for i in range(n):
        for j in range(i + 1, n):
            steps += 1
            if xs[i] == xs[j]:
                pass
    return steps

print("pairs in 4", count_pairs([1, 2, 3, 4]))
print("pairs in 5", count_pairs([1, 2, 3, 4, 5]))

Four items → 6 pair checks. Five → 10. That is n(n-1)/2, which grows like n².

Why it matters

def n_squared(n):
    return n * n

for n in (10, 100, 1000):
    print(n, "scan", n, "pairs", n_squared(n) // 2)

On a kiosk list of 5, both are instant. On 10_000 rows, n² hurts.

Tip

We say “on the order of n” or “on the order of n²”. This course counts exact steps on tiny lists so the shape is visible.