Logarithmic and Square-Root Loops

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.

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.

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

• n
• n / 2
• √n
• log₂ n