Shrestha Pandey

Posted on Oct 11

Why Is My Code Slow? Big-O Explained With Real Timings

#algorithms #timecomplexity #performance #vickybytes

Almost every developer knows Big-O. Many can even say what O(n²) means. But very few have watched the real difference happen on their own machine.

So I ran a small experiment with one simple problem, three ways to solve it, and a stopwatch. The results were bigger than I expected, and I think they explain Big-O better than any textbook.

The problem

You have a list of numbers. Is any number in the list repeated?

This is a real problem which looks like:

checking if two users signed up with the same email
finding duplicate order IDs in a file
making sure every ticket number in a batch is unique

To make the test fair, I used the hardest case: a list with no duplicates at all. That way, every method has to look at the whole list before it can say "no duplicates."

Three ways to solve it

Think of a room full of people, and you want to know if two of them share the same name.

Method 1: Ask everyone about everyone (nested loops).
You take person 1 and compare them with everybody else. Then person 2 with everybody else. And so on. It is easy to understand, and it is how most of us would write it first.

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

Method 2: Sort first (sorting).
You line everyone up in alphabetical order. Now two people with the same name must be standing next to each other. You only have to check neighbors.

def has_duplicates_sorted(items):
    s = sorted(items)
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            return True
    return False

Method 3: Keep a notebook (set).
You walk through the list once. For each person, you check your notebook: "Have I seen this name?" If yes, duplicate found. If no, write it down.

def has_duplicates_set(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

What Big-O says

Big-O tells you how the work grows when the list gets bigger.

Method	Big-O	What it means
Nested loops	`O(n²)`	Make the list 10× bigger, and the work becomes about 100× bigger
Sorting	`O(n log n)`	Make the list 10× bigger, and the work becomes a bit more than 10× bigger
Set (notebook)	`O(n)`	Make the list 10× bigger, and the work becomes about 10× bigger

On paper, these look like small differences. Let's see what they look like on a real computer.

The results

I ran this in Python 3.13 on a normal x86-64 machine. Each number is the best of 3 runs (the 20,000 and 40,000 nested runs are single runs, because they take so long).

List size	Nested loops	Sorting	Set
1,000	0.031 s	0.00019 s	0.00007 s
10,000	2.02 s	0.0019 s	0.0008 s
100,000	skipped	0.024 s	0.013 s
1,000,000	skipped	0.39 s	0.29 s

I skipped nested loops at 100,000 and 1,000,000 on purpose. You'll see why in a moment.

Here is the same data as a picture. Both axes use a log scale, so each step up is ten times bigger. The dashed line is my estimate for nested loops at sizes I didn't wait for.

Result 1: At just 10,000 items, nested loops is already about 2,500 times slower

At 10,000 items, the set finished in under a millisecond. The nested loops took over 2 seconds.

That is roughly 2,500 times slower, for a list that is small by real-world standards. 10,000 rows is a tiny table.

Result 2: Doubling the list makes nested loops about 4 times slower

This is the O(n²) signature. I ran nested loops at a few more sizes to see the curve:

List size	Nested loops time	Compared with previous row
10,000	2.0 s
20,000	7.9 s	about 4× slower
40,000	36.6 s	about 4.6× slower

Every time the list doubled, the time went up about four times. That is exactly what n² predicts: double the input, and you get 2 × 2 = 4 times the work.

Result 3: What would 1,000,000 items cost?

I didn't run it, because I didn't want to wait. But we can estimate using the curve above. At 40,000 items the nested loops needed 36.6 seconds. A list of 1,000,000 is 25 times longer, and n² means 25 × 25 = 625 times the work:

36.6 s × 625 ≈ 22,800 seconds, or about 6 hours

(This is my estimate from the measured curve)

The set version did the same job in 0.29 seconds.

What about sorting vs the set?

Both are fast, and the gap between them is small: at 1,000,000 items, sorting took 0.39 s and the set took 0.29 s.

On paper, the set is O(n) and sorting is O(n log n), so the set should pull ahead as lists grow. It does, but slowly, because the log n part grows very gently.

This is a useful lesson: not every Big-O gap is a disaster. The jump from n² to n log n is huge. The jump from n log n to n is small. Don't lose sleep over the second one until you have measured that it matters.

Why was the nested version so slow?

Count the comparisons. For a list of n items, nested loops make about n × (n − 1) / 2 comparisons:

List size	Comparisons
1,000	about 500 thousand
10,000	about 50 million
1,000,000	about 500 billion

Each time the list got 10× bigger, the number of comparisons got about 100× bigger. At a million items, that is half a trillion comparisons to find out that nothing is repeated.

The set avoids this by trading a little memory for speed. It remembers what it has seen, so each new item needs only one quick lookup instead of a trip through the whole list.

Three lessons I took from this

1. Small test data hides bad code.
At 1,000 items, even the slow method finished in 0.03 seconds. It looked fine. If you only test on a small sample, O(n²) code passes review and breaks in production, when the data grows 100 times.

2. Look for a loop inside a loop.
The fastest way to spot trouble is a loop that contains another loop over the same data. Also watch for hidden loops: in Python, x in some_list is itself a loop. Putting it inside a for loop quietly gives you nested loops.

3. A set (or dictionary) is often the cheapest upgrade.
"Have I seen this before?" is one of the most common questions in code. A set answers it in roughly one step, no matter how big it is. Many slow programs get fast just by swapping a list for a set.

Try it yourself

The whole experiment is one small file. Save it as bench.py and run python3 bench.py. It only needs Python.

Your numbers will be different, because every computer is different. But the shape will be the same: nested loops climbing like a cliff, and the other two staying flat and low.

Try changing the sizes. Try a list that does have duplicates near the start and see how the nested version suddenly gets lucky. Experiments like this teach more than any chart.

Quick cheat sheet

If you see...	It is probably...	Be careful when...
One loop over the data	`O(n)`	rarely a problem
Sorting the data	`O(n log n)`	rarely a problem
A loop inside a loop	`O(n²)`	data can reach tens of thousands of rows
`x in list` inside a loop	`O(n²)` in disguise	you can swap the list for a set