Big O and Algorithm Speed

How fast is "fast"?

Suppose you write two programs that both find a name in a contact list. On your laptop, both feel instant. But one stays instant with a million contacts, while the other takes ten seconds. How could you have known in advance? You cannot judge an algorithm by timing it once on one machine — a faster computer would just make everything quicker. What you really want to know is: as the data grows, how fast does the work grow?

That is exactly what Big O notation measures. It builds directly on the idea of an algorithm from What Is an Algorithm and the searching ideas in Sorting and Searching Algorithms. Big O is the language programmers use to compare algorithms fairly.

The big idea: growth, not stopwatch time

Big O answers one question: if the input size is n, roughly how many steps does the algorithm take? It deliberately throws away details that do not matter for large n — the exact computer, the programming language, and constant factors. What is left is the growth trend.

For example, an algorithm that takes 2n + 5 steps is simply called O(n). Why drop the 2 and the 5? Because when n is a million, the 2n part swamps the +5, and doubling a million is far more important than adding five. Big O captures the part that dominates.

The common growth rates

Here are the four you will meet most, from fastest-growing-slowly to slowest:

Big O	Name	Meaning	Steps when n = 1,000,000
O(1)	constant	Same work no matter the size	1
O(log n)	logarithmic	Work grows very slowly	~20
O(n)	linear	Work grows in step with n	1,000,000
O(n²)	quadratic	Work grows with n squared	1,000,000,000,000

The gap is staggering. At a million items, an O(log n) algorithm does about 20 steps while an O(n²) one does a trillion. Picking the right algorithm is not a small optimisation — it can be the difference between instant and impossible.

O(1): constant time

Some operations take the same time regardless of input size. Looking up a list item by its index is one:

def first_item(items):
    return items[0]      # one step, whether the list has 5 or 5 million items

No loop, no scaling — O(1).

O(n): linear time

If you must look at every item once, the work scales with n. Summing a list is the classic example:

def total(items):
    s = 0
    for item in items:   # runs n times
        s += item
    return s

Double the list and you double the work — O(n).

O(n²): quadratic time

A loop inside a loop, each over the whole list, multiplies the counts. Checking every pair of items for duplicates does this:

def has_duplicate(items):
    for i in range(len(items)):        # n times
        for j in range(i + 1, len(items)):  # up to n times each
            if items[i] == items[j]:
                return True
    return False

For n items, the inner work runs roughly n × n times — O(n²). Fine for short lists, painful for long ones.

O(log n): logarithmic time

The most magical category. Each step throws away half the remaining data, so the work grows incredibly slowly. Binary search on a sorted list does this:

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1     # discard the lower half
        else:
            high = mid - 1    # discard the upper half
    return -1

A million sorted items need only about 20 comparisons, because each step halves the search space: 1,000,000 → 500,000 → 250,000 → ... → 1. That is the power of O(log n).

A complete worked example

This program counts the actual operations of linear search versus binary search, so you can see the difference in cost rather than just trust the labels.

def linear_search(items, target):
    steps = 0
    for i, value in enumerate(items):
        steps += 1
        if value == target:
            return i, steps
    return -1, steps

def binary_search(items, target):
    steps = 0
    low, high = 0, len(items) - 1
    while low <= high:
        steps += 1
        mid = (low + high) // 2
        if items[mid] == target:
            return mid, steps
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, steps

data = list(range(1, 1_000_001))   # a sorted list of 1,000,000 numbers
target = 999_999                   # near the end, the worst case for linear

print("Linear:", linear_search(data, target)[1], "steps")   # ~999,999
print("Binary:", binary_search(data, target)[1], "steps")   # ~20

Reading the output: linear search inspects items one by one, so finding a value near the end of a million-item list costs nearly a million steps — that is O(n). Binary search repeatedly halves the range, reaching the same value in around 20 steps — that is O(log n). Same data, same answer, but the binary search does roughly fifty thousand times less work. This is Big O made real.

Try it yourself

1. Time it. Wrap each search in Python's time.perf_counter() and measure the real seconds. The step counts predict which is faster.
2. Shrink the data. Set the list to just 10 items. Notice the two searches are almost identical now — Big O differences only matter as n grows.
3. Classify some code. For each snippet, decide the Big O: a single loop over a list; two separate (not nested) loops; a loop inside a loop. (Answers: O(n), O(n), O(n²).)

Challenge: Write a function count_pairs(items) that prints every pair of items in a list using nested loops, and confirm by counting that it does about n²/2 operations. Then research one O(n log n) sorting algorithm (like merge sort) and explain in a sentence why it sits neatly between the O(n) and O(n²) rows of the table above.