Measuring Algorithms Without a Stopwatch

Growth, not seconds

Timing a program tells you how fast it ran on one machine, with one input, in one language, on one day. Change any of those and the number changes. Algorithm analysis asks a more durable question: how does the amount of work grow as the input grows? We describe input size with n (the number of elements in an array, characters in a string, vertices in a graph) and count the basic operations an algorithm performs (comparisons, assignments, arithmetic) as a function of n. If doubling the input doubles the work, the algorithm scales linearly; if doubling the input quadruples the work, it scales quadratically, and for large inputs that difference dwarfs any difference in hardware. Complexity analysis lets you compare algorithms on paper, predict whether a solution will finish in time for a given input size, and explain design choices in interviews and code reviews. It complements, but does not replace, measuring real performance.

Growth curves diverge

For small inputs most algorithms look similar; as n grows, the curves separate dramatically.

Two ways to check for duplicates

Both are correct; their growth is very different.

def has_duplicate_pairs(items):
    # compare every pair: about n*n/2 comparisons
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] == items[j]:
                return True
    return False

def has_duplicate_set(items):
    # one pass with a set: about n hash operations
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

# for 100,000 items: roughly 5,000,000,000 comparisons vs roughly 100,000 set operations

Hardware does not fix bad growth

A computer ten times faster lets a quadratic algorithm handle only about three times larger inputs in the same time. Improving the growth rate usually beats buying faster machines.

Quick check: What does complexity analysis primarily describe?

• How the work grows as the input size grows
• The exact running time in seconds
• The number of lines of code
• The programming language used