Comparing two approaches

The same job, two ways to do it

Once you know that Big-O measures the shape of growth, you can use it to settle a very ordinary argument: given two programs that both do the job, which one should you keep? "It works" is not the answer, because both work. The useful question is how each one behaves when the input stops being small.

Picture a community event. You have a guest list of everyone who was invited, and as the evening goes on people show up at the door one by one. For each arrival you want a quick yes or no: is this person on the list? We will write two versions and then reason about them.

Approach one: scan the list every time

The most direct idea is to keep the guest list as a plain Python list and, for every arrival, look through it.

def check_arrivals_slow(guests, arrivals):
    admitted = []
    for person in arrivals:
        if person in guests:      # this scans the whole list
            admitted.append(person)
    return admitted

The in test on a list is not free. Python has to walk through the names until it finds a match or reaches the end. If the guest list has n names and there are m arrivals, each arrival may cost up to n comparisons, so the whole thing is about m * n work. When the two lists grow together, that is O(n²) territory.

Approach two: build a set first

Now do one bit of preparation. Before the doors open, pour the guest list into a set, which is built to answer "is this in here?" almost instantly.

def check_arrivals_fast(guests, arrivals):
    guest_set = set(guests)       # one pass to build it
    admitted = []
    for person in arrivals:
        if person in guest_set:   # roughly one step
            admitted.append(person)
    return admitted

Building the set is one pass over the guest list, so n steps. After that, each of the m arrivals costs roughly one step instead of n. The total is about n + m, which is O(n) when the lists grow together.

Reasoning about which one scales

Both functions return the same admitted list, so testing them on ten names tells you nothing. The difference only shows up at size. Say the guest list and the arrivals are each 500 people. The first approach does roughly 500 × 500 = 250,000 comparisons. The second does roughly 500 + 500 = 1,000 steps. Same answer, and one is done before the other has warmed up.

The second version does pay a small price: the set is a separate copy of the names, so it uses extra memory. For a guest list that is a bargain. That trade, a little more memory to change n² work into n work, is one you will make again and again, and Big-O is what lets you see it clearly before you commit.

Before moving on, look back at any loop you have written that runs an in test on a list: would turning that list into a set change its Big-O, and what would that speed cost you in memory?

Check yourself

1. Both functions produce exactly the same list of admitted guests. Why is that not enough to decide which one to keep, and what question do you ask instead?
2. In the first approach, where does the hidden cost come from, and why does it turn a single loop over the arrivals into roughly n² work overall?
3. The fast version builds a set, which uses extra memory. Describe how you would explain to someone why that memory is worth spending here.