Lesson 2 of 16

Compare the Amount of Work

Execution time varies with input and other activity even on the same machine. First compare how operation counts grow with input size.

Pair every two distinct items

Count each pair once, treating A-B and B-A as the same pair.

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

print(count_pairs(5))

The result is 10: the first item has four partners, then three, two, and one. In general there are n(n-1)/2 pairs, giving O(n²) time.

Do not just count visible loops

• Two consecutive loops may perform n + n operations, which is O(n).
• If a loop repeatedly halves its remaining work, its count is not simply n.
• A function call may hide sorting or copying work.

Big O O is an upper growth bound, omega Ω a lower bound, and theta Θ a matching upper and lower order. These are separate from best, average, and worst cases. Even a worst-case cost has upper and lower bounds.

Time and space are different costs

This code counts pairs without storing them. A fixed number of variables gives O(1) extra space. Storing every pair would require O(n²) output space as well as time.

Our basic analysis treats comparing or adding individual numbers as constant-cost operations. For very large integers or long strings, the lengths of the values also matter.

Check your understanding

If input grows from 1,000 to 2,000, how much does work proportional to n² grow? Does O(n) always mean faster in practice?