# Single, Nested and Dependent Loops — Time & Space Complexity (Big-O)

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

> Derive the complexity of single, nested and triangular 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.

![A square grid fully shaded beside a square grid with only the lower-left triangle shaded.](assets/figures/big-o/section-3-map.svg) — Figure 3.1 — n² iterations versus n(n − 1)/2 iterations.

## Counting iterations in loops

Comments give the number of times the inner statement runs.

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

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

- [x] O(n²)
- [ ] O(n)
- [ ] O(n log n)
- [ ] O(n³)

*Answer:* O(n²). The inner loop runs n + (n−1) + … + 1 = n(n+1)/2 times in total, which is O(n²).