# Logarithmic and Square-Root Loops — Time & Space Complexity (Big-O)

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

> Recognise halving, doubling and square-root loop patterns.

## When the loop variable multiplies

If a loop variable is **multiplied or divided** by a constant each iteration, the loop runs a logarithmic number of times. `i = 1; while i < n: i *= 2` takes i through 1, 2, 4, 8 … and stops after about **log₂ n** steps. Likewise `while n > 1: n //= 2` halves n each time, which is the heart of **binary search**: each comparison discards half of the remaining range, so at most about log₂ n + 1 comparisons are needed. The base does not matter for the complexity class (tripling also gives O(log n)). A loop such as `i = 1; while i * i <= n: i += 1` runs about **√n** times, the pattern behind checking whether a number is prime by trial division. Combining patterns multiplies: an outer loop of n iterations with an inner halving loop is **O(n log n)**; an outer halving loop with an inner loop of n iterations is also O(n log n). But an inner loop whose length halves each outer iteration sums to n + n/2 + n/4 + … < 2n, which is **O(n)**, a classic trick question.

## Logarithmic and square-root patterns

Each comment gives the iteration count.

```python
def doubling(n):
    i = 1
    while i < n:          # i = 1, 2, 4, ... -> about log2(n) iterations -> O(log n)
        i *= 2

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:       # range halves each time -> O(log n)
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:     # about sqrt(n) iterations -> O(sqrt n)
        if n % d == 0:
            return False
        d += 1
    return True

def halving_inner(n):
    size = n
    while size > 0:       # outer: log n times
        for _ in range(size):   # n + n/2 + n/4 + ... < 2n in total
            pass
        size //= 2        # overall O(n), not O(n log n)
```

## Guessing a number

In "guess my number from 1 to 1,000", each "higher or lower" answer halves the possibilities, so you never need more than 10 guesses. Going up to a million only needs 20. That is logarithmic growth.

**Quiz:** How many iterations does `i = n; while i > 1: i = i // 2` perform, roughly?

- [ ] n
- [ ] n / 2
- [ ] √n
- [x] log₂ n

*Answer:* log₂ n. Halving n repeatedly reaches 1 after about log₂ n steps.