Algorithmic Complexity and Measured Performance

A procedure that is fast for ten items may be unusable for a million. Conversely, two implementations with the same asymptotic complexity can have very different running times. Complexity describes growth as input size increases; benchmarking measures time under specific conditions. Use both to choose where an improvement is worth making.

First define what n measures

Define the input size before stating a complexity bound. The number of array elements and the number of digits in an integer are different measures of n. Counting basic operations also requires assumptions. A model that counts fixed-width integer addition as one operation differs from a model that processes each digit of an arbitrarily large integer. State the model that fits the question.

def total(values):
    result = 0
    for value in values:
        result += value
    return result

def pair_count(values):
    count = 0
    for x in values:
        for y in values:
            if x == y:
                count += 1
    return count

The first function visits each of n elements once, so its time is Θ(n) if each basic operation takes constant time. The second visits n values of y for each x, making n² comparisons and taking Θ(n²) time. Multiplying n by ten therefore multiplies the dominant work by roughly ten in the first case and one hundred in the second. Other factors affect elapsed time, so these are not exact promises about measured ratios.

O is an upper bound; Θ describes a tight growth rate

O(g(n)) is an asymptotic upper bound: for sufficiently large n, the cost does not exceed some constant multiple of g(n). Θ(g(n)) bounds the cost above and below by positive constant multiples. The function 3n+7 is Θ(n), but O(n²) is also a valid, looser upper bound. Informal discussion often uses O to mean a representative growth rate; precise analysis distinguishes a valid upper bound from a tight one.

Common growth rates include constant, logarithmic, linear, n log n, quadratic, and exponential. Binary search needs logarithmically many comparisons because each step approximately halves the candidate range. About twenty comparisons suffice to narrow a million candidates. Remember the assumptions: the data is sorted, and the middle element can be accessed in constant time.

Worst-case, average-case, and amortized analysis ask different questions

Worst-case complexity considers the most expensive input of a given size. Average-case analysis requires a distribution specifying which inputs occur with which probabilities. “It is usually fast” does not supply that distribution. Amortized analysis spreads the total cost of a sequence over its operations and does not necessarily assume random inputs.

For example, a dynamic array that doubles its capacity sometimes needs to copy elements during an append. Across n appends, however, the total number of copies can be bounded by O(n), giving amortized O(1) cost per append. This is compatible with a particular resizing append taking worst-case O(n) time. That individual delay still matters when response-time limits are strict.

Space and constant factors also shape the design

Space complexity describes how memory requirements grow. Distinguish total space, including the input, from auxiliary space used in addition to it. Copying every element needs Θ(n) auxiliary space; retaining only an accumulated sum normally needs Θ(1) under the usual fixed-size-value model. Time and space can be traded, for example by storing results to avoid recomputation.

Two Θ(n) procedures can interact with caches differently if one reads a contiguous array and the other follows pointers to scattered locations. Function calls, string allocations, and I/O also contribute constant factors. A simple implementation may win for small inputs, while one with better asymptotic growth wins as inputs become larger.

Keep measurement conditions comparable

python -m timeit -s "xs = list(range(10000))" "sum(xs)"

Separate the measured work from its preparation, and compare equivalent results with the same input and implementation environment. Repeat short operations and examine variation across runs. timeit is useful for small benchmarks, but it does not automatically reproduce production latency, garbage collection, or network load. In a live service, latency percentiles and concurrency also matter.

Check your understanding

• Does a nested loop always take Θ(n²) time? No. Its iteration ranges and early exits determine the total. Count the sum of the actual iteration counts.

• Does amortized O(1) append mean every individual append takes constant time? No. It is an evaluation across a sequence, and a particular operation may still be expensive.

• Is an O(n) procedure always faster than an O(n log n) procedure? Not for every finite input. Constant factors and implementation conditions can reverse the comparison. Measure multiple input sizes and inspect the growth trend as well.

Concepts in this unit: Time complexity · Amortized analysis · Benchmark ·

Read next: Caches and the Memory Hierarchy