Algorithmic Complexity

Why measure growth, not seconds

The obvious way to compare two algorithms is to time them. But a timing says as much about the computer as about the algorithm: the same program runs at different speeds on a laptop and a server, in Python and in C, on a quiet machine and a busy one. And a timing for 1,000 items tells you little about what happens with a million.

Time complexity answers a more useful question: as the input grows, how does the amount of work grow? An algorithm whose work doubles when the input doubles will always, for large enough inputs, beat one whose work quadruples — whatever hardware either runs on. This is what "scalability" means in practice.

Counting steps

To measure growth, count the basic steps an algorithm performs — comparisons, additions, assignments — as a function of the input size, called n. Each basic step is assumed to take a fixed amount of time. The example below counts the steps of three common loop shapes:

def count_steps(n):
    single = 0
    for i in range(n):              # one loop over the input
        single += 1

    nested = 0
    for i in range(n):              # a loop inside a loop
        for j in range(n):
            nested += 1

    halving = 0
    size = n
    while size > 1:                 # halve the problem each time
        size //= 2
        halving += 1

    return single, nested, halving


for n in [10, 100, 1000]:
    single, nested, halving = count_steps(n)
    print(f"n = {n:>4}: single {single:>4}  nested {nested:>9,}  halving {halving}")

n =   10: single   10  nested       100  halving 3
n =  100: single  100  nested    10,000  halving 6
n = 1000: single 1000  nested 1,000,000  halving 9

The three shapes grow completely differently. Multiply the input by 10 and the single loop does 10 times the work, the nested loop 100 times, and the halving loop only about 3 steps more. That pattern of growth — not the exact numbers — is what complexity captures.

Big O notation

Big O notation is the standard shorthand for growth. Writing that an algorithm is O(n²) (say "order n squared" or "big O of n squared") means: for large inputs, its number of steps grows at most in proportion to n². Formally, a step count f(n) is O(g(n)) if some constant multiple of g(n) is at least f(n) for every n beyond some point. Big O is an upper bound: it promises the growth is no worse than that.

Two rules follow from that definition:

• Drop constant factors. 3n and 100n are both O(n). Constants depend on the language and the machine; the shape of the growth does not.
• Keep only the fastest-growing term. For large n, the largest term dominates so completely that the others stop mattering.

Take an algorithm that performs 3n² + 5n + 2 steps:

The lower-order terms fade away, and the factor 3 does not change the shape, so the algorithm is simply O(n²). Big O is deliberately rough: it tells you how an algorithm scales, not how fast it is on small inputs, where an O(n²) algorithm with a small constant can beat an O(n log n) one.

Common complexity classes

A handful of growth rates cover most algorithms you will meet, listed here from best to worst:

How far apart these are becomes clear when you put in numbers. The table shows the step count for each class (logarithms are base 2 and rounded; the base only changes a constant factor, so it does not matter for Big O):

Even at a billion steps per second, 1.27 × 10³⁰ steps would take about 4 × 10¹³ years — thousands of times the age of the universe. Exponential algorithms are usable only for tiny inputs.

Best, average and worst case

The number of steps often depends on the data, not only on its size. Linear search in a list of n items finds the target in 1 step if it is first — the best case — and needs all n steps if it is last or missing — the worst case. If the target is equally likely to be anywhere, the average case is about n/2 steps, which is still O(n).

Complexity is normally quoted for the worst case, because it is a guarantee: the algorithm will never do worse. The best case is rarely useful on its own. The average case matters when the worst case is rare, as with quicksort, which is O(n²) in the worst case but O(n log n) on average — see Searching and Sorting for a comparison table.

Space complexity

Space complexity describes how the memory an algorithm needs grows with its input, in the same notation. Usually only the extra memory is counted, beyond the input itself. Reversing a list in place needs O(1) extra space — just a couple of index variables — while building a reversed copy needs O(n):

def reverse_in_place(items):          # O(1) extra space
    left, right = 0, len(items) - 1
    while left < right:
        items[left], items[right] = items[right], items[left]
        left += 1
        right -= 1


def reversed_copy(items):             # O(n) extra space: a whole new list
    return items[::-1]

Recursion uses space too: every call that has not returned yet occupies a frame on the call stack, so a recursion n levels deep needs O(n) space even when it creates no lists. Time and space can often be traded: memoization spends memory on stored results to save time, and a hash table uses more memory than a plain list in exchange for fast lookups.

Amortized cost

Some operations are usually cheap but occasionally expensive. A dynamic array, such as a Python list, has room for a few extra items; appending is O(1) until the room runs out, and then the whole array is copied to a larger block, which is O(n). The amortized cost spreads those rare expensive steps over all operations. Because the array grows by a factor each time, the copies add up to only a few per append on average. This simulation of an array that doubles when full counts the copied items:

def simulate_appends(count):
    capacity, size, copied = 1, 0, 0
    for _ in range(count):
        if size == capacity:        # full: move everything to a block twice as big
            copied += size
            capacity *= 2
        size += 1
    return copied


for count in [1_000, 1_000_000]:
    copied = simulate_appends(count)
    print(f"{count:>9,} appends: {copied:>9,} items copied, "
          f"{copied / count:.2f} per append")

    1,000 appends:     1,023 items copied, 1.02 per append
1,000,000 appends: 1,048,575 items copied, 1.05 per append

So appending is O(1) amortized: any single append may be slow, but a long run of appends costs O(1) each on average. CPython grows lists by a smaller factor than 2 to waste less memory, with the same result.

In practice: list or set?

Complexity is not just theory; it decides everyday choices. Testing whether a value is in a list is a linear search, O(n). Testing it in a set is a hash table lookup, O(1) on average. The example below counts the equality comparisons each one makes, using a small class that reports every comparison:

class Tracked:
    """A number that counts how often it is compared for equality."""
    comparisons = 0

    def __init__(self, value):
        self.value = value

    def __eq__(self, other):
        Tracked.comparisons += 1
        return self.value == other.value

    def __hash__(self):
        return hash(self.value)


for n in [1_000, 100_000]:
    as_list = [Tracked(i) for i in range(n)]
    as_set = set(as_list)
    target = Tracked(n - 1)          # the last item: worst case for the list

    Tracked.comparisons = 0
    target in as_list
    list_steps = Tracked.comparisons

    Tracked.comparisons = 0
    target in as_set
    set_steps = Tracked.comparisons

    print(f"n = {n:>7,}   list: {list_steps:>7,} comparisons   set: {set_steps}")

n =   1,000   list:   1,000 comparisons   set: 1
n = 100,000   list: 100,000 comparisons   set: 1

The set goes straight to the right bucket and compares once; the list compares against every item. If a program checks membership many times, converting the list to a set once is usually the single most effective speed-up available. See Dictionaries and Sets for the Python details.

Common pitfalls

Nested loops over the same data

A loop inside a loop over the same data is O(n²), and it is easy to write without noticing — especially when the inner "loop" is hidden in an in test or a list.index() call. Checking a list for duplicates by comparing every pair is the classic case; remembering what you have seen in a set turns it into a single pass:

def has_duplicates_pairs(values):      # compare every pair: O(n²)
    steps = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            steps += 1
            if values[i] == values[j]:
                return True, steps
    return False, steps


def has_duplicates_set(values):        # one pass with a set: O(n)
    seen = set()
    steps = 0
    for value in values:
        steps += 1
        if value in seen:
            return True, steps
        seen.add(value)
    return False, steps


for n in [10, 100, 1000]:
    values = list(range(n))            # no duplicates: the worst case
    _, pair_steps = has_duplicates_pairs(values)
    _, set_steps = has_duplicates_set(values)
    print(f"n = {n:>4}: pairs {pair_steps:>7,} steps   set {set_steps:>5,} steps")

n =   10: pairs      45 steps   set    10 steps
n =  100: pairs   4,950 steps   set   100 steps
n = 1000: pairs 499,500 steps   set 1,000 steps

Repeated string concatenation

In many languages — Java, C#, Go and Python among them — strings are immutable. Then text = text + piece does not extend the string; it builds a new one and copies all the old characters into it. Doing that in a loop copies 1, then 2, then 3 … characters, for a total of about n²/2: an O(n²) loop that looks like O(n). The fix is to collect the pieces and join them once, which is O(n): "".join(pieces) in Python, a StringBuilder in Java and C#, strings.Builder in Go.