Tricky Loop Patterns

Beyond the textbook shapes

Some loops need a little more maths. Harmonic loops: for i in range(1, n+1): for j in range(i, n+1, i): has an inner loop that runs about n/i times, so the total is n(1 + 1/2 + 1/3 + … + 1/n), and the harmonic series grows like ln n, giving O(n log n); the Sieve of Eratosthenes has a similar structure (its tighter bound is O(n log log n)). Early exits (break, return) affect the best and average case but usually not the worst case. Two-pointer loops, where two indices each move forward at most n times in total, are O(n) even though they look nested, because the total movement is bounded. Similarly, a nested while inside a for can be linear overall if the inner loop's total iterations across the whole run are bounded by n (as in sliding-window algorithms). When in doubt, ask: how many times, in total, can the inner statement execute over the entire run? That question, rather than the loop shape, gives the answer.

Loops that look quadratic but are linear

The inner pointer only ever moves forward, so total work is bounded by n.

def longest_unique_substring(s):
    seen = {}
    left = best = 0
    for right, ch in enumerate(s):            # right moves n times in total
        while ch in seen and seen[ch] >= left:   # left also moves at most n times in total
            left += 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best
# overall O(n): each index enters and leaves the window at most once

def harmonic(n):
    count = 0
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):           # about n / i iterations
            count += 1
    return count                              # about n * ln(n) -> O(n log n)

Count total work, not loop depth

Nesting depth is only a hint. Amortised reasoning about how far pointers move, or how many times each element is processed, often reveals that a nested loop is linear.

Quick check: In a sliding-window algorithm, the right pointer advances n times and the left pointer advances at most n times in total. What is the overall complexity?

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