# Tricky Loop Patterns — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/l-patterns

> Analyse harmonic loops, early exits and loops over changing data.

## 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.

```python
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.

**Quiz:** 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)
- [x] O(n)
- [ ] O(log n)

*Answer:* O(n). Total pointer movement is at most 2n, so the work is linear.