Performance & Recursion

How can you count all the participants in an auditorium if you don’t have sensors, check-in processes or access control?

Option 1: Use my eyes and my mind to count them one by one: 1,2,3,4…
Option 2: Count by twos, like 2,4,6,8,…
Option 3: Ask the participants to follow these instructions:
1. Stand up and think of the number 1
2. Pair off with someone standing, add their number to yours, and remember the sum
3. One of you should then sit down
4. If still standing, go back to step 2. The final person standing will know the exact number of participants.

Option 3 is the most efficient and faster than the other methods. This is why algorithms are important.

That’s how the conference by David Malan begins. Malan is a Computer Science professor at Harvard University, and he’s teaching how different ways of solving problems can lead to disaster or simply become a small everyday hurdle.

Performance and Complexity

Performance tells you how much slower a program becomes as the input grows. If I have 10 records to process, it takes x time. But if I have 1 million records, will it take 1,000,000 * x time, or could it be different? This is known as Big O notation.

In the example of counting people in a room, it would be something like this:

Option 1 is O(n) (Linear time). It takes as many steps as there are people. If there are 100 participants, this takes 100 steps
Option 2 is O(n/2), still linear but slightly faster.
Option 3 is O(log n) (Logarithmic time). If there are 100 participants, just takes 7 steps, because the number of people standing reduces by half in each round.

Recursion

What makes option 3 the winning option? ✨ The recursion ✨ Recursion is when a function calls itself to solve a smaller version of the same problem.

Every recursive function needs a Base Case to avoid running forever. Think of it as a ‘Divide and Conquer’ strategy: break the problem down until it’s simple enough to solve

The Matryoshka Doll (The Logic) Think of recursion like a Russian nesting doll. To find out how many dolls are inside, you don’t just look at the big one; you follow these rules:

The Recursive Step: Open the current doll. If there is another one inside, repeat the process.
The Base Case: Eventually, you reach the smallest doll that cannot be opened. This is where you stop and start counting back.

def factorial(n):
    if n == 0:
        return 1  # base case
    return n * factorial(n - 1)  # recursive case

factorial(4)
→ 4 * factorial(3)
→ 4 * 3 * factorial(2)
→ 4 * 3 * 2 * factorial(1)
→ 4 * 3 * 2 * 1 * factorial(0)
→ 4 * 3 * 2 * 1 * 1
→ 24

The CS50 Auditorium (The Efficiency)

David Malan uses a clever way to count people in a room. Instead of counting 1, 2, 3… (O(n)), he uses a recursive strategy:

Stand up and assign yourself the number 1.
Pair off with someone else standing.
Add your numbers together, and one person sits down.
Repeat until only one person is left standing.

Why it works:

The problem is cut in half in every round. If you have 1,000 people, you only need about 10 rounds to find the total. This is the power of Logarithmic Time (O(log n)).