🎯 HOOK

The Handshake Problem

You're at a party with 5 people. Everyone shakes hands with everyone else once. That's 10 handshakes. Now there are 10 people. How many handshakes?

🧪 EXPLORE

Watch Nested Loops Fill a Grid

Each cell represents comparing two items. See how the work explodes as n grows!

Total cells to fill: 25

Steps
0
Expected (n²)
25

Key Insight: Change n from 5 to 10. The cells don't just double—they quadruple! (25 → 100)

💡 EXPLAIN

What is O(n²)?

Quadratic time means the steps grow proportional to the square of amount of data.

📊

Think of it like a grid or table

  • ✓ Nested loops (loop inside a loop)
  • ✓ Comparing every item to every other item
  • ✓ Bubble sort, selection sort
  • ✓ Finding all pairs in a set
# Classic O(n²) pattern
for i in range(n):
  for j in range(n):
    # Do something with i and j

⚠️ Warning: O(n²) becomes impractical quickly. n=100 → 10,000 steps. n=1,000 → 1,000,000 steps!

Growth Examples

n Steps (n²)
10100
10010,000
1,0001,000,000

How to Optimize

  • • Use hash maps (O(n) instead)
  • • Sort first, then use binary search
  • • Look for better algorithms
  • • Avoid nested loops when possible
✏️ PRACTICE

Test Your Understanding

1. Which operation is O(n²)?

2. An O(n²) program takes 4 seconds for n=100. How long for n=200?

3. What's the speed of this code?

for i in range(len(items)):
    for j in range(i + 1, len(items)):
        if items[i] == items[j]:
            return True
return False

4. How can you optimize duplicate detection from O(n²) to O(n)?

5. True or False: Two separate loops = O(n²)

for i in range(n): # ...
for j in range(n): # ...

6. Real-world scenario: Which sorting program would you avoid for 1 million items?

7. Pattern recognition: Spot the O(n²)

for x in items: for y in items: compare(x, y)
🤔 REFLECT

Think Deeper

💭 Why does nested loop speed multiply (n × n) instead of add (n + n)?

💭 Can you think of a problem that requires O(n²) with no better solution?

🎉

Excellent Work!

You now understand O(n²) quadratic time — and why it's crucial to avoid nested loops at scale.