Single, Nested and Dependent Loops

Counting iterations

The complexity of loop-based code comes from counting how many times the innermost statements run. A single loop from 0 to n with constant work inside is O(n); a loop that steps by a constant, such as i += 2, is still O(n) because it runs n/2 times. Independent nested loops multiply: two loops of n iterations each give n · n = O(n²), and three give O(n³). Dependent nested loops, where the inner loop's range depends on the outer variable, need a sum. For for i in range(n): for j in range(i):, the inner body runs 0 + 1 + 2 + … + (n − 1) = n(n − 1)/2 times, which is still O(n²): only the constant halves. Loops that run a fixed number of times regardless of n, such as iterating over 26 letters, are O(1). Watch out for hidden loops inside library calls: x in some_list, list.index, slicing and string concatenation all take time proportional to the data involved.

Rectangle versus triangle of work

Independent nested loops cover an n × n square; dependent loops cover a triangle, about half of it.

Counting iterations in loops

Comments give the number of times the inner statement runs.

def single(n):
    for i in range(n):            # n times            -> O(n)
        pass

def step_by_two(n):
    for i in range(0, n, 2):      # n / 2 times        -> O(n)
        pass

def nested(n):
    for i in range(n):
        for j in range(n):        # n * n times        -> O(n^2)
            pass

def triangular(n):
    for i in range(n):
        for j in range(i):        # 0 + 1 + ... + (n-1) = n(n-1)/2 -> O(n^2)
            pass

def fixed(n):
    for letter in "abcdefghijklmnopqrstuvwxyz":   # 26 times, independent of n -> O(1)
        pass

Sum of 1 to n is about n²/2

Memorise 1 + 2 + … + n = n(n + 1)/2. It appears constantly: pairs of elements, insertion and selection sort, building strings character by character. All of them are quadratic.

Quick check: What is the complexity of `for i in range(n): for j in range(i, n): work()` with constant-time work?

• O(n²)
• O(n)
• O(n log n)
• O(n³)