Logarithms and nested loops

What are time and space complexity?

Time complexity describes how the amount of work grows when the input gets larger. Space complexity describes how much memory an algorithm needs. They describe growth, rather than an exact number of seconds or bytes. Here, n usually means the number of input items.

Example: Reading one known array position takes O(1), or constant work. Visiting every item takes O(n), or work proportional to the number of items. Keeping a second copy of n items takes O(n) extra space.

Helpful before this chapter

If these ideas are new, begin with:

Programming foundations

Understand the idea

Repeated division by a fixed factor leads to logarithms. Nested loops multiply only when their iteration counts justify it. Follow how the inner bound depends on outer state.

Work through an example

8→4→2→1 takes three halvings. Doubling i from 1 while i<n takes ceil(log₂ n) steps for n>1; scanning n elements each time gives Θ(n log n).

Time and space complexity

Halving is Θ(log n) for n≥2; an n-sized inner scan gives Θ(n log n).

Why it works

After t halvings, the remaining scale is roughly n/2^t.

Common mistakes

Exponentially growing loop values do not imply linear iterations.
Handle zero and singleton inputs separately.

Chapter lab · Python implementation

Analyze growth before optimizing constants. The lab separates direct work, nested work, and repeated halving. Count iterations explicitly so asymptotic claims can be checked. Unless stated otherwise, n is input length, arithmetic fits a machine word, and auxiliary space excludes input but includes temporary collections.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def counts(n):
    if n < 0:
        raise ValueError('n must be nonnegative')
    linear = sum(1 for _ in range(n))
    pairs = sum(1 for i in range(n) for j in range(i))
    halvings, x = 0, n
    while x > 1:
        x //= 2
        halvings += 1
    return linear, pairs, halvings

def doubling_copies(n):
    size, capacity, copied = 0, 1, 0
    for _ in range(n):
        if size == capacity:
            copied += size
            capacity *= 2
        size += 1
    return copied

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert counts(0) == (0,0,0)
assert counts(8) == (8,28,3)
assert counts(5) == (5,10,2)
assert doubling_copies(9) == 15
assert all(doubling_copies(n) < 2*n for n in range(1,100))

CHECK YOUR UNDERSTANDING