Skip to content
wannacode

Big-O: how the work grows

In short: Big-O describes how the work of an algorithm grows as the data grows, ignoring constants: O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ).

Problem

Will it hold up with a million?

The shop signed a contract with a big supplier. In a month the catalogue grows from 1,000 to 1,000,000 products. There are six functions in the code that every product or every payment goes through:

  • the first price in the list (for the banner on the home page);
  • searching for a price in the sorted price list;
  • the sum of the prices (for the report);
  • sorting the prices (for the "cheapest first" page);
  • the double payment check from the previous lesson;
  • all combinations of products that fit in the customer's budget.

Which ones will hold up? There is no data with a million products yet, and the seconds on your laptop lie anyway. You have to tell from the code. Counting every step exactly, as with n(n − 1) / 2, is slow. And the details do not matter: what matters is how the work grows.

The idea

Big-O: what doubling does

Big-O is a short name for how the number of operations grows when n (the amount of data) grows. It does not say seconds, it says a shape: what happens to the work when the data doubles.

Class Name Example from the shop n doubles → the work
O(1) constant the first price does not change
O(log n) logarithmic searching the sorted price list one step more
O(n) linear the sum of the prices ×2
O(n log n) "n log n" sorting a bit over ×2
O(n²) quadratic double payments ×4
O(2ⁿ) exponential all combinations within budget squared

Here are the six functions. The prices are in euro cents, so they are whole numbers:

def first_price(prices):
    return prices[0]
def total(prices):
    result = 0
    for p in prices:
        result += p
    return result
def double_payments(ids):
    found = 0
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            if ids[i] == ids[j]:
                found += 1
    return found

first_price makes one step, however many prices there are. total makes one per price. double_payments makes one per pair.

See it

O(log n): how many times you halve

Searching the sorted price list looks at the middle. If the price you want is bigger, the left half is not needed at all and is thrown away. Otherwise the right half goes. So after every check half is left:

def index_of(ordered, price):
    lo = 0
    hi = len(ordered) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if ordered[mid] == price:
            return mid
        elif ordered[mid] < price:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

How many checks if the price is not there? As many times as you can halve n before nothing is left. That is the logarithm: log₂ n is "how many times you halve".

for n in [1000, 100000, 1000000, 1000000000]:
    halvings = 0
    left = n
    while left > 0:
        left //= 2
        halvings += 1
    print(n, "→", halvings)
Output
1000 → 10
100000 → 17
1000000 → 20
1000000000 → 30

A thousand times more prices (from 1,000 to 1,000,000) is only 10 checks more. Doubling adds one. That is why O(log n) barely grows.

More about the boundaries of binary search (and where it goes wrong by one) comes in the lesson Binary search.

See it

O(n log n) and O(2ⁿ)

Sorting uses the built-in sorted:

def sorted_prices(prices):
    return sorted(prices)

Good sorting algorithms split the array into halves (log n levels) and on every level go through everything once (n steps). That is why they are O(n log n). How exactly, you will see in the lesson on merge sort.

The combinations within budget: for every product there are two choices, "take it" or "leave it". That is why combos calls itself twice:

def combos(prices, i, total, budget):
    if i == len(prices):
        return 1 if total <= budget else 0
    return (combos(prices, i + 1, total, budget)
            + combos(prices, i + 1, total + prices[i], budget))

With 1 product there are 2 combinations, with 2 there are 4, with 3 there are 8. Every new product doubles everything there was so far. That is O(2ⁿ).

All six, run on five prices and five payments:

prices = [1299, 450, 3999, 899, 2450]
sorted_list = sorted_prices(prices)
payments = [100231, 100232, 100233, 100232, 100234]
print("First price: " + str(first_price(prices)))
print("2450 is at index " + str(index_of(sorted_list, 2450)))
print("Total: " + str(total(prices)))
print("Cheapest: " + str(sorted_list[0]) + ", most expensive: " + str(sorted_list[4]))
print("Double payments: " + str(double_payments(payments)))
print("Combinations up to 5000: " + str(combos(prices, 0, 0, 5000)))
Output
First price: 1299
2450 is at index 3
Total: 9097
Cheapest: 450, most expensive: 3999
Double payments: 1
Combinations up to 5000: 18

See it

What doubling does

def combos(prices, i, total, budget):
    if i == len(prices):
        return 1 if total <= budget else 0
    return (combos(prices, i + 1, total, budget)
            + combos(prices, i + 1, total + prices[i], budget))
Step by step, in words
  1. The first price: one step with 4 prices and with 8. The work does not depend on n: O(1).
  2. Binary search looks at the middle and throws away half. 4 → 2 → 1 is 3 checks, 8 → 4 → 2 → 1 is 4. Twice the prices, one check more: O(log n).
  3. The sum visits every price once: 4 and 8 steps. Twice the prices, twice the work: O(n).
  4. Sorting merges level by level (here merge sort, as in Bench). There are log n levels, with at most n comparisons on each: 5 → 16. O(n log n).
  5. Double payments: every one with every one after it. 6 → 28: the triangle grows in two directions. O(n²).
  6. Combinations within budget: every product is "take it" or "leave it", and every new one doubles them. 16 → 256: with 8 products the work is the work for 4, squared. O(2ⁿ).

The six classes with 4 and with 8 prices. Every cube is one step, exactly as many as Bench counts. O(1) does not move. O(log n) adds one bar. O(n) doubles. O(n log n) doubles and gets one more level. O(n²) grows in two directions. O(2ⁿ) turns from a 4 × 4 square into a 16 × 16 square.

The idea

Constants and small terms drop out

The double payment report makes n(n − 1) / 2 = n²/2 − n/2 steps. Why is it O(n²) and not O(n²/2 − n/2)?

The smaller term disappears as n grows:

n n²/2 n/2 n/2 as a share of the total
10 50 5 10%
1,000 500,000 500 0.1%
100,000 5,000,000,000 50,000 0.001%

The constant does not change the shape. n²/2 and n² grow the same way: twice the data, four times the work. A constant is like a slower machine: it changes the seconds, but not what happens when the data doubles. And you already know that seconds lie.

So Big-O keeps only the fastest growing term, without the number in front of it: 3n + 5 is O(n), n²/2 − n/2 is O(n²), 2n log n + 7n is O(n log n).

More precisely, if you are curious

The exact definition: f(n) is O(g(n)) if there is a constant c and a threshold n₀ such that f(n) ≤ c · g(n) for every n ≥ n₀. That is, from some n on, f does not grow faster than g, up to a constant. So O(n) is also O(n²) (it is an upper bound), but we say the tightest one. There is also Θ (exactly that much) and Ω (at least that much). In conversations and interviews "O(n)" usually means Θ(n).

The base of the logarithm is not written either: log₂ n and log₁₀ n differ by a constant (log₂ n ≈ 3.32 · log₁₀ n).

See it

The six curves in the browser

Run the six functions in Bench. The axis is logarithmic: every mark is ×10. O(n) is a straight line, O(n²) is twice as steep, and O(2ⁿ) takes off right away.

  • The first price O(1)
  • Binary search O(log n)
  • The sum of the prices O(n)
  • Sorting (merge sort) O(n log n)
  • Every pair of orders O(n²)
  • Every combination within budget O(2ⁿ)
Algorithmn = 10n = 1,000n = 100,000
The first price111
Binary search41017
The sum of the prices101,000100,000
Sorting (merge sort)218,7091,536,371
Every pair of orders45499,500≈ 4,995,000,000
Every combination within budget1,024≈ 10³⁰¹≈ 10³⁰¹⁰²
The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

The answer for the million products: the first price, the search, the sum and the sorting will hold up. The double payments become 500 billion steps and have to move to the set from the previous lesson. And all combinations of a million products cannot be listed on any computer: 2 to the power of a million is a number with 301,030 digits.

More precisely, if you are curious

What the built-in sort uses in each language. sorted and list.sort are TimSort (since Python 3.11 with an improved merge policy, Powersort). O(n log n), and on almost sorted data close to O(n). Bench counts the comparisons of merge sort, because the built-in one cannot be counted from the outside. The class is the same.

Try it

Predict the output

The outer loop runs n = 8 times. The inner one halves until nothing is left. What does the program print?

n = 8
steps = 0
for i in range(n):
    left = n
    while left > 0:
        left //= 2
        steps += 1
print(steps)
Answer

Try it

Find the hidden loop

The function counts the different customers in the orders of the month. It has only one loop, and yet with 100,000 orders it is as slow as the double payment report:

def unique_customers(orders):
    seen = []
    for customer in orders:
        if customer not in seen:
            seen.append(customer)
    return len(seen)
orders = [7, 3, 7, 12, 3, 7]
print(unique_customers(orders))
Output
3

On which line is the second loop hiding?

Pick the line with the bug.

Exercise

How many combinations

Solve the task in your editor.

The steps of the combinations. Add a counter steps to combos: one step for every finished combination (when i reaches the end). Run it with 10, 11 and 12 products with prices of 500 + 100 · k cents and a budget of 5000, and print the steps:

Output
10 products: 1024 steps
11 products: 2048 steps
12 products: 4096 steps

Every product doubles the steps. How many are there with 20 products? And with 40? Work it out before you run it.

More tasks

  • The class of every function. Write the Big-O of every function from the lesson "Time complexity: counting steps", including the sales by product (50 products × n orders).
  • Binary search with a counter. Add a counter to index_of and search for a price that is not there in 1,000 and in 100,000 sorted prices. Compare with the program that halves.
  • A set again. Fix the counting of different customers with a set and compare the steps with 1,000 different customers.

Test

Check yourself

1. A function makes 3n + 5 steps. What is its complexity?
2. An algorithm is O(n²). The data becomes 10 times bigger. How many times more work should you expect?
3. How many checks does binary search make in a sorted list of 1,000,000 prices when the price is not there?
4. The combinations within budget are O(2ⁿ). How many are there with 30 products?
5. Two algorithms for the same task: one is O(n log n), the other O(n²). With 10 elements the second one is faster. Which one do you pick for 1,000,000 orders?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·