Reading Complexity Straight Off the Loops

"Ninety percent of reading Big-O is reading loops. Sequential loops add. Nested loops multiply. Almost everything else is a footnote."

The Two Rules That Do the Heavy Lifting

You don't need calculus to find an algorithm's complexity. You need to find the loops and apply two rules:

Sequential loops add. A loop over n, then another loop over n, is n + n = 2n = O(n). One after the other, you add — and then drop the constant.
Nested loops multiply. A loop over n with another loop over n inside it is n × n = O(n²). Three deep is O(n³). Inside multiplies.

So the whole game becomes: find the deepest nesting, because the most-multiplied term is the one that dominates. A function with a triple-nested loop and fifty separate single loops is O(n³) — the single loops are noise next to the cube.

The log n Surprise

One loop shape breaks the pattern and it's worth memorizing: a loop that cuts the remaining work in half each step is O(log n), not O(n). If you start at n and halve to n/2, n/4, n/8 … you reach 1 in about log₂(n) steps. For a billion items that's only 30 steps. This is the secret behind binary search and balanced trees, and it's why "log n" feels like cheating the first time you see it.

To read complexity: find the loops. Sequential loops add (keep the biggest). Nested loops multiply (count the depth). A halving loop is log n. That covers most code you'll ever analyze.

The Trap: Hidden Loops

The deadliest O(n²) hides in code that looks like a single loop. Write if x in my_list inside a loop, and you've nested a loop — because in on a list secretly scans the whole list. One visible loop, one invisible loop, n² total. The same trap lurks in slicing inside a loop, building a string with += in a loop, or calling list.insert(0, ...) repeatedly. Knowing the cost of the operations you call is half of complexity analysis — the Python wiki link below is worth bookmarking.

Pippa's Confession

I once "optimized" a function down to a single clean loop and proudly called it O(n). Dad pointed at one line: if item in seen_list. That innocent in was scanning a growing list every iteration — my pretty single loop was quietly O(n²). I swapped seen_list for a set and it became truly O(n). The loops you can see aren't always the loops you've got.

Code

Six functions, six complexities·python

# Read the complexity of each. The answer is in the loop structure.

def a(items):                       # O(n): one loop
    for x in items:
        print(x)

def b(items):                       # O(n): two SEQUENTIAL loops -> n + n
    for x in items: print(x)
    for x in items: print(x)

def c(items):                       # O(n^2): NESTED loops -> n * n
    for x in items:
        for y in items:
            print(x, y)

def d(items):                       # O(log n): work halves each step
    n = len(items)
    while n > 1:
        n = n // 2
        print(n)

def trap(items):                    # LOOKS O(n), is actually O(n^2)!
    seen = []
    for x in items:
        if x in seen:               # 'in' on a list = a hidden inner scan
            continue
        seen.append(x)

def trap_fixed(items):              # O(n): set membership is O(1)
    seen = set()
    for x in items:
        if x in seen:               # 'in' on a set = no hidden loop
            continue
        seen.add(x)

Exercise

Hand-analyze: a function loops over a list of n items; for each item it does a .index() lookup on the same list (which scans to find a value), then appends to a result. What's the real complexity, and which line is the hidden loop? How would you make it O(n)?

Hint

.index() scans the list — that's an inner O(n) inside your visible O(n) loop. A dict mapping value→position, built once up front, kills the hidden scan.

The Two Rules That Do the Heavy Lifting

The log n Surprise

The Trap: Hidden Loops

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0