Time and Space Complexity Practice

Q: How do I practice time and space complexity?

Define the input sizes, count the repeated operation, and inventory the maximum live memory. State the bound and its assumptions aloud. Then change one constraint and work through the count again. Start with two of the six drills here per session.

Q: Do nested loops always mean O(n²)?

No. The total work depends on the ranges. Independent sizes can give O(nm), a halving or doubling range can give O(log n), and the sum 1 + 2 + 4 + … up to n is O(n). Count the work rather than the indentation levels.

Q: Does space complexity include the returned answer?

Say which convention you are using. This guide reports auxiliary space excluding input and returned output, then reports output space separately. Peak extra space includes both. A returned list with n elements still takes O(n) storage even when the algorithm needs only O(1) other state.

Q: Are Python dictionary lookups always constant time?

No. Expected constant time assumes well-distributed hashes and bounded-cost hashing and equality. Collisions can make one lookup linear in the number of stored keys. Long strings or large integers also add costs that the simplified word model here excludes.

Start here

Explain the count before naming the bound

Define the input sizes. A list length, number of requests, and string length are different quantities. Keep independent sizes separate.
Choose the case and cost model. Say whether you mean worst-case or expected time. Count comparisons, copied references, or loop visits; do not infer a bound from a stopwatch alone.
Add or sum the actual work. Sequential phases add. Nested ranges may multiply, shrink, or form a series. Include work hidden inside slicing, sorting, membership, and helper calls.
Inventory peak live storage. Include temporary copies and call stacks. Report auxiliary space and returned output separately, so the listener knows what you excluded.

The assumptions used in these drills

Inputs already satisfy each contract. Arithmetic, integer comparison, and an index or counter occupy constant-cost machine words. Python integers can grow arbitrarily large; real bit costs break that simplification for very large values. List appends use amortized constant time, meaning occasional resizing is spread across a sequence of appends. Dictionary costs are qualified separately.

Big O describes an asymptotic upper bound; Θ describes a tight growth bound in the chosen model. Neither predicts exact milliseconds. A function that visits every element has linear growth even when a faster machine makes the measured time small.

Try before revealing

Six drills that reward an explanation

For each snippet, write down the result for the example, the repeated-operation count, time, auxiliary space, and output space. Then open the answer. Assertions are silent when they pass; run them after the function in a local Python 3 interpreter.

Drill 1

Two scans, two input sizes

Input and output. a and b are lists of integers. Let n = len(a) and m = len(b). Return the number of positive values across both lists; do not change either list.

def count_positive(a, b):
    count = 0
    for value in a:
        if value > 0:
            count += 1
    for value in b:
        if value > 0:
            count += 1
    return count

assert count_positive([2, -1, 0], [3, 4]) == 3
assert count_positive([], []) == 0
assert count_positive([], [-2, 8]) == 1

Explain aloud. Count comparisons with zero. Does having two loops multiply the sizes? What if one list is much longer?

Reveal drill 1 analysis and follow-up

Count and bound

There are exactly n + m comparisons with zero. The loops run one after another, so time is Θ(n + m + 1), commonly written O(n + m). Auxiliary space and scalar output are both O(1) words. Do not replace both sizes with n unless you explicitly define n as the combined size or assume m is bounded by n.

Change one assumption

If the second loop moved inside the first, it would perform n × m comparisons of b's values, plus n comparisons of a's values. That version would also count b repeatedly, changing the result. Complexity analysis does not establish correctness.

Drill 2

A triangle of pairs, and a growing answer

Input and output. labels is a list of n short strings. Return every pair of distinct positions i < j, in increasing i then j order. Repeated labels still count as different positions. Tuples reference the original strings.

def review_pairs(labels):
    pairs = []
    for i in range(len(labels)):
        for j in range(i + 1, len(labels)):
            pairs.append((labels[i], labels[j]))
    return pairs

assert review_pairs(["A", "B", "C"]) == [("A", "B"), ("A", "C"), ("B", "C")]
assert review_pairs(["A", "A"]) == [("A", "A")]
assert review_pairs([]) == []
assert review_pairs(["A"]) == []

Explain aloud. Write the sum of inner-loop visits. Is 'constant extra space' an adequate description of this function?

Reveal drill 2 analysis and follow-up

Count and bound

The append runs (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 times. Time is Θ(n²) as n grows, using amortized constant-time list append. The answer holds Θ(n²) fixed-size tuples and references. Auxiliary state excluding that answer is O(1); peak extra space including output is Θ(n²). Empty and singleton inputs return an empty list.

Change one assumption

If you only need the number of pairs, return n * (n - 1) // 2 in O(1) word-model time and space. If you yield pairs lazily, producing all pairs still takes Θ(n²) time, but retained output can stay small when the caller consumes one pair at a time.

Drill 3

Nested loops with a geometric total

Input and output. n is a nonnegative integer. Return the number of inspection slots in batches of sizes 1, 2, 4, …, stopping before a batch would exceed n. The returned integer is an operation counter.

def inspection_slots(n):
    width = 1
    visits = 0
    while width <= n:
        for _ in range(width):
            visits += 1
        width *= 2
    return visits

assert inspection_slots(0) == 0
assert inspection_slots(1) == 1
assert inspection_slots(5) == 7
assert inspection_slots(8) == 15

Explain aloud. The outer loop is logarithmic. Is multiplying that by n a tight description of the total work?

Reveal drill 3 analysis and follow-up

Count and bound

For n ≥ 1, let k = floor(log₂ n). The inner loop runs 1 + 2 + … + 2ᵏ = 2ᵏ⁺¹ − 1 times. That count lies between n and 2n − 1. Time is Θ(n), with O(1) auxiliary words and O(1) output words. O(n log n) is an upper bound but misses the tighter linear bound. For n = 0 the function does constant work.

Change one assumption

Change range(width) to range(n). Now every round scans n slots, so the counter is n × (floor(log₂ n) + 1) for n ≥ 1, giving Θ(n log n) time as n grows. State what work repeats before choosing a formula.

Drill 4

Find a boundary without copying

Input and output. values is a sorted, nondecreasing list of n integers; target is an integer. Return the first index whose value is at least target, or n if none exists. Empty input returns 0. The list stays unchanged.

def first_at_least(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

assert first_at_least([2, 4, 4, 9], 4) == 1
assert first_at_least([2, 4, 4, 9], 10) == 4
assert first_at_least([2, 4, 4, 9], 1) == 0
assert first_at_least([], 4) == 0

Explain aloud. Which interval can still contain the answer? Why are duplicate values safe? Where would copying change your analysis?

Reveal drill 4 analysis and follow-up

Count and bound

Indices below lo contain values less than target; indices at or above hi contain values at least target. Each iteration shrinks the undecided interval by about half. The two bounds meet at the first valid position, including across duplicates. Worst-case time is Θ(log(n + 1)); auxiliary and output space are O(1) words. No sorted copy or recursive call stack is created.

Change one assumption

Calling sorted(values) first would add sorting time and a copy. Slicing out half the list each round would also add linear total copying along the search path. A logarithmic number of comparisons alone does not make the whole implementation logarithmic. Python's bisect documentation similarly distinguishes logarithmic search from linear list insertion.

Drill 5

A dictionary is an assumption, not magic

Input and output. allowed and requests are lists of bounded-length strings. Let n and m be their lengths, and u the number of distinct allowed strings. Return one Boolean per request, preserving request order and duplicates.

def permission_flags(allowed, requests):
    lookup = {}
    for name in allowed:
        lookup[name] = True
    result = []
    for name in requests:
        result.append(name in lookup)
    return result

assert permission_flags(["read", "write", "read"], ["write", "delete", "write"]) == [True, False, True]
assert permission_flags([], ["read"]) == [False]
assert permission_flags(["read"], []) == []

Explain aloud. Include building the lookup, the output list, and the hash-table assumption. What changes if allowed remains a list?

Reveal drill 5 analysis and follow-up

Count and bound

Expected time is O(n + m) under well-distributed hashes and bounded-cost key operations. Auxiliary space is O(u), output is O(m), and peak extra space is O(u + m). A conservative collision worst-case bound is O(n² + nm + m + 1), because building the table and each membership test can scan stored keys; constructing m result flags still takes O(m) when n is zero. This is an expected improvement, not an unconditional linear-time guarantee.

Change one assumption

Testing each request directly against the allowed list costs O(nm + m + 1) in the worst case and uses O(1) auxiliary space beyond the returned flags. For just one request, building the dictionary also costs O(n) expected time. Explain the memory and repeated-query tradeoff before choosing the lookup.

Drill 6

One loop hiding many copies

Input and output. values is a list of n integers. Return the total length of all suffixes starting at positions 0 through n − 1. Slices make new lists of references; integer objects themselves are not copied.

def suffix_slots(values):
    total = 0
    for start in range(len(values)):
        suffix = values[start:]
        total += len(suffix)
    return total

assert suffix_slots([7, 8, 9]) == 6
assert suffix_slots([7]) == 1
assert suffix_slots([]) == 0

Explain aloud. How many references are copied overall? Are all those copies alive at once? Can you compute the answer without a slice?

Reveal drill 6 analysis and follow-up

Count and bound

The slices copy n + (n − 1) + … + 1 = n(n + 1)/2 references. Time is Θ(n²), even though there is only one explicit loop. Peak auxiliary space is O(n), not O(n²), because previous slices are replaced. During an assignment, the previous and new slice can briefly coexist; both together are still O(n). The returned scalar occupies O(1) words.

Change one assumption

Replace len(suffix) with len(values) - start and remove the slice to get O(n) time with O(1) auxiliary space. Returning n * (n + 1) // 2 removes the loop as well, giving O(1) time under the stated word model. The function computes a count; it does not need to construct the suffixes.

A 25-minute rehearsal

Minutes 0–3. Choose two drills. State all input sizes and the cost model before solving.
Minutes 3–15. Spend six minutes per drill. Trace an empty input and a small nonempty input, derive the count, and explain peak memory.
Minutes 15–21. Open the answers and run the assertions. Repair one mistaken count; avoid rewriting a correct explanation just to match our wording.
Minutes 21–25. Answer one changed-assumption follow-up without looking. Record whether you solved it independently, needed a hint, or still need another attempt.

This timing is an editorial practice suggestion, not an employer standard. A useful review note is “I counted the comparisons but missed the copied slices,” followed by the corrected count.

Apply the analysis in three timed coding exercises, then use the follow-up question drills to defend a changed constraint. Return to the practice library for behavioral and system-design sessions.

Sources and editorial method

The snippets, counts, explanations, and session plan are original ClawPad practice material. They are not employer questions. The examples and operation-count formulas were executed locally; those checks support the examples, while the written derivations explain their general growth.

Python bisect performance notes distinguish logarithmic search from linear insertion.
Python design FAQ describes hash-table dictionary access and its hash assumptions.
Python’s archived CPython complexity reference documents list slicing, append amortization, and hash-table worst cases. These are implementation assumptions, not a promise for every Python runtime.
Python’s data structures tutorial explains list operations and copies.

References checked October 12, 2026. The page teaches operation growth, not measured runtime or hiring outcomes.

Common questions

How do I practice time and space complexity?

Define the input sizes, count the repeated operation, and inventory the maximum live memory. State the bound and its assumptions aloud. Then change one constraint and work through the count again. Start with two of the six drills here per session.

Do nested loops always mean O(n²)?

No. The total work depends on the ranges. Independent sizes can give O(nm), a halving or doubling range can give O(log n), and the sum 1 + 2 + 4 + … up to n is O(n). Count the work rather than the indentation levels.

Does space complexity include the returned answer?

Say which convention you are using. This guide reports auxiliary space excluding input and returned output, then reports output space separately. Peak extra space includes both. A returned list with n elements still takes O(n) storage even when the algorithm needs only O(1) other state.

Are Python dictionary lookups always constant time?

No. Expected constant time assumes well-distributed hashes and bounded-cost hashing and equality. Collisions can make one lookup linear in the number of stored keys. Long strings or large integers also add costs that the simplified word model here excludes.