Big-O Notation at the Grocery Store

· 3 min read · Syed Omar Faruk Towaha
Big-O Notation at the Grocery Store

Big-O notation sounds like something you'd need a whiteboard and a stern professor for. It's really just a way of answering one question: if the problem gets bigger, how much more work do I have to do?

Let's go shopping.

O(1): you know exactly where the milk is

You walk in, turn left, grab the milk. It doesn't matter whether the store has 100 products or 100,000; it takes the same time. That's constant time.

In code: looking up a key in a dictionary or hash map.

prices = {"milk": 2.49, "eggs": 4.99}
prices["milk"]   # O(1), on average

O(log n): the aisles are sorted

The store is arranged alphabetically and you're looking for "Paprika." You go to the middle (M), realise P is later, jump to the middle of the second half, and so on. Every step cuts the remaining store in half. Double the size of the store, and you need just one more step.

In code: binary search.

import bisect

items = sorted(all_items)
i = bisect.bisect_left(items, "paprika")

A million sorted items? About 20 steps. That's the power of halving.

O(n): checking every shelf

The store has no signs and you're looking for eggs. You walk every aisle until you find them. Twice as many aisles, twice as much walking.

In code: a loop over a list.

def find(items, target):
    for item in items:          # O(n)
        if item == target:
            return True
    return False

O(n²): comparing every item with every other item

You want to know whether any two products have the same price. So you pick up the first product and compare it with every other product. Then the second product with every other product. And so on, until closing time, and then the next morning.

# O(n^2): every pair
def has_duplicate_price(products):
    for a in products:
        for b in products:
            if a is not b and a.price == b.price:
                return True
    return False

# O(n): remember what you've seen
def has_duplicate_price_fast(products):
    seen = set()
    for p in products:
        if p.price in seen:
            return True
        seen.add(p.price)
    return False

With 10 products, nobody cares. With 100,000 products, the first version does about 10 billion comparisons and the second does 100,000.

Growth curves
Log scale. O(n²) leaves the building quickly.

Things Big-O doesn't tell you

The practical rule

You don't need to analyse every function. You need a little alarm that goes off when you see a loop inside a loop over data that can grow. That alarm has saved more production systems than any amount of hardware. Also, ask a staff member where the eggs are. Sometimes the best algorithm is asking.

// related

// prefer the terminal?

Open the terminal blog and type read big-o-at-the-grocery-store.