The program that worked until it did not

A student writes an attendance checker for her class. Given the list of students and the list who turned up, print who is absent.

absent = []
for student in all_students:
    if student not in present:
        absent.append(student)

Sixty students. It runs instantly. She is done.

The next term the college asks for the same thing across the whole department. Twelve hundred students. It still runs, in about a second, and she notices but does not mind.

The year after, it is the whole college. Forty thousand students. The program now takes four minutes, and nobody can tell her why, because not one line of it changed.

What happened

student not in present looks like one operation. It is not. It walks the list until it finds a match or runs out.

So the real work is: for every student, scan every present student.

The input grew 666 times. The work grew 444,000 times.

The one line fix

present = set(present)      # this line

Now in takes the same time whether the set holds ten names or ten million, and forty thousand students finishes in well under a second.

That is the subject. Not memorising structures: knowing which one turns a program that will not finish into one that does.