Big-O and Complexity Analysis

Why we don’t measure in seconds

Suppose you write a program and want to know if it is fast enough. The obvious idea is to run it and time it with a stopwatch. That works, but the number you get is almost useless for comparing methods, because it depends on things that have nothing to do with your idea:

• The hardware: a new laptop runs the exact same code several times faster than an old phone.
• The language and setup: the same logic in one language, or with a busy machine, gives a different time every run.
• The input size: timing a program on 10 items tells you little about how it behaves on 10 million items.

What we actually care about is a more stable question: as the input gets bigger, how fast does the work grow? A method that takes twice as long when the input doubles is fundamentally different from one that takes four times as long, no matter whose computer runs it. That growth pattern is what survives when you change machines, and it is what Big-O notation describes.

A quick vocabulary note, since we assume no prior background:

• An algorithm is a fixed step-by-step procedure for solving a problem (for example, “look at each name in the list until you find the one you want”).
• An operation is one small unit of work: a comparison, an addition, reading one item from a list.
• We use the letter n for the size of the input (the number of items you are working with). When we say “as n grows,” we mean “as the list gets longer.”

Counting operations

The trick behind complexity analysis is to stop timing and start counting operations as a function of n. We do not count exactly; we count roughly, because the shape of the growth is what matters.

Here is a program that adds up the numbers in a list.

def total(numbers):
    result = 0                 # 1 operation
    for x in numbers:          # runs n times
        result = result + x    # 1 operation each time -> n operations
    return result              # 1 operation

print(total([10, 20, 30]))     # -> 60

If the list has n items, the loop body runs n times, so the work is roughly n operations plus a couple of fixed ones. We would say this is “on the order of n” operations. Double the list and the work roughly doubles. That linear relationship is the important fact.

Now a program with a loop inside a loop, which checks whether any two different people in a list share the same name.

def has_duplicate(names):
    for i in range(len(names)):        # runs n times
        for j in range(len(names)):    # runs n times for EACH i
            if i != j and names[i] == names[j]:
                return True            # found a match
    return False

print(has_duplicate(["ana", "bo", "ana"]))  # -> True
print(has_duplicate(["ana", "bo", "cy"]))   # -> False

Here the inner loop runs n times, and it does that for each of the n outer steps. That is n * n = n^2 operations in the worst case. Double the list and the work roughly quadruples. This is a very different growth pattern from the first example, and Big-O is how we name that difference.

What Big-O means

Big-O notation describes the upper bound on how the work grows as n grows large, ignoring constant factors and small terms. We write it as O(...) with the growth pattern inside:

• The first program above is O(n) (“order n,” or linear time).
• The second is O(n^2) (“order n squared,” or quadratic time).

Two deliberate simplifications are built into this, and they are features, not sloppiness:

• Drop the constants. Whether the loop body does 1 operation or 5, the work still grows in proportion to n. So 5n and n are both O(n). We care about the shape of the growth, not the exact multiplier, because the multiplier depends on the machine and the shape does not.

• Drop the lower-order terms. If a program does n^2 + n + 100 operations, then for large n the n^2 term dwarfs everything else. When n is one million, n^2 is a trillion while n is only a million. So n^2 + n + 100 is simply O(n^2). We keep only the fastest-growing term.

# All three of these are O(n): the growth is proportional to n.
def a(xs):
    return [x + 1 for x in xs]        # one pass  -> ~n work

def b(xs):
    for x in xs: pass
    for x in xs: pass                 # two passes -> ~2n work, still O(n)

def c(xs):
    return xs[0] if xs else None      # 3n + 7 would still be O(n)

The common complexity classes

These are the growth patterns you will meet again and again, ordered from fastest (best) to slowest (worst).

O(1) — constant time

The work does not depend on n at all. Whether the list has 10 items or 10 million, it takes the same fixed number of steps. Reading one item from a list by its position is the classic example.

def first(xs):
    return xs[0]        # jumps straight to position 0, no scanning

print(first([9, 8, 7]))  # -> 9

Big-O: O(1) time. Getting bigger input does not make this slower.

O(log n) — logarithmic time

The work grows very slowly: each step throws away half of the remaining input. A logarithm (base 2) answers the question “how many times can I halve n before I reach 1?” For a million items that is only about 20 steps; for a billion, about 30. That is why O(log n) is considered excellent.

The everyday example is binary search: finding a value in a sorted list by repeatedly checking the middle and discarding the half that cannot contain the target.

def binary_search(sorted_xs, target):
    lo, hi = 0, len(sorted_xs) - 1
    while lo <= hi:
        mid = (lo + hi) // 2          # middle position
        if sorted_xs[mid] == target:
            return mid                # found it
        elif sorted_xs[mid] < target:
            lo = mid + 1              # discard the left half
        else:
            hi = mid - 1              # discard the right half
    return -1                         # not present

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # -> 3
print(binary_search([1, 3, 5, 7, 9, 11], 4))  # -> -1

Big-O: O(log n) time. Each loop pass halves the search range, so the number of passes is the number of halvings.

O(n) — linear time

The work grows in direct proportion to n: double the input, roughly double the work. Any method that must look at every item once, like summing a list or finding the largest value, is O(n).

def largest(xs):
    best = xs[0]
    for x in xs:            # must inspect every item
        if x > best:
            best = x
    return best

print(largest([3, 9, 2, 7]))  # -> 9

Big-O: O(n) time. You cannot find the maximum of unsorted data without looking at all of it.

O(n log n) — linearithmic time

A bit slower than linear, but still very usable. This is the speed of the good sorting algorithms. Intuitively, they do about log n rounds of work, and each round touches all n items. Python’s built-in sorted runs in O(n log n).

def sort_copy(xs):
    return sorted(xs)      # Python's built-in sort: O(n log n)

print(sort_copy([5, 2, 8, 1]))  # -> [1, 2, 5, 8]

Big-O: O(n log n) time. When you see this on a sorting or divide-and-conquer method, it is expected and good.

O(n^2) — quadratic time

The work grows with the square of n: double the input and the work quadruples. This is the signature of a loop nested inside another loop where both run over the whole input, as in the duplicate-name checker earlier. It is fine for small inputs and painful for large ones.

def all_pairs(xs):
    pairs = []
    for a in xs:           # n times
        for b in xs:       # n times each -> n^2 total
            pairs.append((a, b))
    return pairs

print(all_pairs([1, 2]))  # -> [(1, 1), (1, 2), (2, 1), (2, 2)]

Big-O: O(n^2) time. If n is in the thousands this is usually still okay; in the millions it is hopeless.

O(2^n) — exponential time

The work doubles every time you add one item to the input. This grows so fast that even modest inputs become impossible. It shows up in naive solutions that try every possible combination. The classic teaching example is the naive recursive Fibonacci, which recomputes the same values over and over.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)   # two calls each level -> ~2^n calls

print(fib(10))   # -> 55
# fib(50) would take an impractically long time this way.

Big-O: roughly O(2^n) time. Adding one to n roughly doubles the work. Anything exponential is a warning sign that you need a better approach.

How the classes compare as n grows

The whole point is that these classes pull apart as n gets large. Ordered from the fastest-growing (avoid) at the top to the slowest-growing (best) at the bottom, they line up like this:

flowchart TD
    A["O(2^n) exponential — explodes"]
    B["O(n^2) quadratic — slow for big n"]
    C["O(n log n) linearithmic — good sorting"]
    D["O(n) linear — one pass"]
    E["O(log n) logarithmic — halving"]
    F["O(1) constant — free"]
    A --> B --> C --> D --> E --> F
    A -.->|worst| F

To feel the gulf between the classes, look at roughly how many operations each one implies as n grows. These are rough counts, not exact.

Notice how O(log n) barely moves while O(2^n) leaves the page almost immediately. That gap is the reason this whole subject exists.

How to read loops quickly

Most complexity analysis in practice comes down to reading loops. A few reliable rules:

• A single loop over the input is O(n). It runs the body once per item.
• A loop nested inside another loop, each over the input, multiplies: O(n) * O(n) = O(n^2). Three deep would be O(n^3).
• A loop that halves the remaining work each pass (like binary search, where you cut the range in two) is O(log n).
• Two loops one after another (not nested) add: O(n) + O(n) = O(2n) = O(n). Sequential work is added, then simplified.
• Constant work with no loop over n is O(1).

# O(n): one pass
for x in data:
    process(x)

# O(n^2): nested passes
for x in data:
    for y in data:
        compare(x, y)

# O(n): two separate passes, added not multiplied -> still linear
for x in data:
    step_one(x)
for x in data:
    step_two(x)

The key distinction is nested (multiply) versus sequential (add). Nesting is what turns linear into quadratic.

Time complexity versus space complexity

Everything above measured time complexity: how the number of operations grows. There is a second axis, space complexity, which measures how the amount of extra memory grows with n. “Extra” is the important word: we usually count only the memory the algorithm allocates itself, not the input it was handed.

def double_in_place(xs):
    for i in range(len(xs)):
        xs[i] = xs[i] * 2        # reuses the existing list
    return xs
# Time: O(n)  (one pass)
# Space: O(1) (no new list; a couple of variables regardless of n)

def doubled_copy(xs):
    return [x * 2 for x in xs]   # builds a brand-new list of size n
# Time: O(n)  (one pass)
# Space: O(n) (the new list grows with the input)

Both functions are O(n) in time, but they differ in space: one works in place using O(1) extra memory, the other builds a new list of size n, so it uses O(n) extra memory. There is often a trade-off, using more memory to save time or the reverse, and being able to name both costs is what lets you make that choice deliberately.

Amortized cost, briefly

Sometimes a single operation is occasionally expensive but almost always cheap, and the honest way to describe it is the average cost per operation over a long run. That average is called the amortized cost.

The standard example is appending to a Python list with .append(). Most appends just drop the item into a spot that is already reserved, which is O(1). Once in a while the list runs out of reserved room and has to move everything into a bigger block, which is O(n). But because that expensive move happens rarely and reserves a lot of extra room each time, the cost spread across all the appends is still O(1) per append. We say .append() runs in amortized O(1) time.

xs = []
for i in range(1000):
    xs.append(i)   # each append is amortized O(1); the whole loop is O(n)

print(len(xs))     # -> 1000

The takeaway: when you see “amortized,” it means the worst single case is slower, but the long-run average is what is quoted, and it is trustworthy for total-cost reasoning.

Common pitfalls

• Big-O is about growth, not a stopwatch. An O(n^2) method can beat an O(n) method on small inputs because of constant factors. Big-O only tells you who wins as n gets large. For tiny, fixed inputs it may not matter at all.
• It usually describes the worst case. binary_search returning on the very first check is a lucky best case; the O(log n) figure is the guarantee when things do not go your way. Unless stated otherwise, assume Big-O means worst case.
• Nested loops are not automatically O(n^2). What matters is how many times each loop actually runs. An inner loop that runs a fixed 3 times regardless of n keeps the whole thing O(n). Read what the loop bounds actually depend on.
• Hidden loops count. Calling something like x in a_list looks like one step but scans the list, so it is O(n) on its own. Put it inside a loop over n items and you have quietly built an O(n^2) method. Know the cost of the operations you call, not just the loops you write.
• Do not keep the constants and small terms. O(2n + 5) is not a real answer; simplify it to O(n). The whole notation exists to strip those away.

Practice

1. State the time complexity of this function in Big-O terms, and explain in one sentence why: it loops once over a list of n numbers and, for each number, loops again over the whole list to count how many others are smaller.

2. Write a function that returns True if a list is sorted in non-decreasing order and False otherwise. What is its time complexity, and what is its extra-space complexity?

3. You have two functions that both solve the same problem: one is O(n) time using O(n) extra memory, the other is O(n log n) time using O(1) extra memory. Describe one situation where you would prefer each, given what you now know about trading time against space.