AI Hints
Home›DSA in Python Tutorial›Big O in Code
DSA in Python · Lesson 8 of 132

O(n²): Nested Loops

When work multiplies.

⏱ 2 min read▶ Video at 7:58🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Put one loop inside another, and the work multiplies. For every item, you look at every other item. It's fine for a hundred items. For a hundred thousand, it can take hours.

O(n²): Nested Loops
From the video: O(n²): Nested Loops
  • A loop inside a loop
  • The work multiplies
  • Fine small, terrible big

Finding duplicates, slowly

Here's a simple way to check for duplicates. Compare every number with every number after it. The inner loop runs for each step of the outer loop. We count the comparisons. Run it. Ten times more items gives about one hundred times more work. That's O of N squared.

nested.pypython
def has_duplicate(nums):
    checks = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            checks += 1
            if nums[i] == nums[j]:
                return True, checks
    return False, checks

for n in [100, 1000]:
    print(n, "items:", has_duplicate(list(range(n)))[1], "checks")
Output
100 items: 4950 checks
1000 items: 499500 checks

Finding duplicates, fast

Now a better way. A set remembers what we've seen, and checking a set is O of one. So one loop is enough. The whole thing is O of N. Run it. A million numbers, checked in a blink.

fast_dupes.pypython
def has_duplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return True
        seen.add(n)
    return False

print(has_duplicate(list(range(1_000_000))))
print(has_duplicate([3, 1, 4, 1, 5]))
Output
False
True

Summary

Nested loops are usually O of N squared. A set or a dictionary can often turn that into O of N. Next, the magic of halving.

Key takeaways
  • Loop in a loop: O(n²)
  • A set can fix it
  • O(n) instead
Next up: O(log n): Halving — the power of cutting in half