Practice Problems

Complexity analysis gets faster with practice. These five problems train reading a complexity, improving it, and confirming it by measurement. Try each one before reading the approach and solution.

Problem 1. Name the complexity

Give the time complexity of each function. In c, result is a list.

def a(n):
    total, i = 0, 1
    while i < n:
        for _ in range(n):
            total += 1
        i *= 2
    return total

def b(n):
    total = 0
    for _ in range(n):
        j = 1
        while j * j <= n:
            total += 1
            j += 1
    return total

def c(items):
    result = []
    for x in items:
        if x not in result:
            result.append(x)
    return result

def d(n):
    if n <= 1:
        return 1
    return d(n // 2) + d(n // 2)

Approach: count outer and inner iterations separately and multiply; write a recurrence for recursion.

• a: i doubles, so the outer loop runs about log n times around an inner loop of n. O(n log n)
• b: the inner loop runs while j ≤ √n, so O(n√n), that is O(n^1.5)
• c: x not in result scans the list. With all values distinct that is 0 + 1 + ... + (n-1) comparisons, O(n²). Adding a set makes it O(n).
• d: it looks logarithmic, but T(n) = 2T(n/2) + O(1) is O(n) by the master theorem. Counting calls confirms it:

calls = 0

def d_counted(n):
    global calls
    calls += 1
    if n <= 1:
        return 1
    return d_counted(n // 2) + d_counted(n // 2)

for n in (1_024, 2_048, 4_096):
    calls = 0
    d_counted(n)
    print(n, calls)   # 2047, 4095, 8191: twice the n, twice the calls

Problem 2. First repeated value

Return the value whose second occurrence comes earliest, or None. In [4, 7, 1, 7, 4] the answer is 7, because 7 repeats before 4 does.

Approach: comparing all pairs is O(n²). Scan once and keep seen values in a set; set lookups are O(1) on average, so the whole scan is O(n) time and O(n) space.

def first_repeat(items):
    seen = set()
    for x in items:
        if x in seen:
            return x
        seen.add(x)
    return None

print(first_repeat([4, 7, 1, 7, 4]))  # 7
print(first_repeat([1, 2, 3]))        # None

If memory is tight and you only need to know whether any duplicate exists, sort and compare neighbours in O(n log n) time instead. Pick based on whether time or memory is scarcer.

Problem 3. A pair with difference k

Given a list of integers sorted in ascending order and an integer k ≥ 0, decide whether two elements differ by exactly k. Aim for O(n).

Approach: keep two indices i < j. If the difference is smaller than k, advance j to grow it; if larger, advance i to shrink it. Each index moves at most n times, so the scan is O(n).

def has_pair_with_difference(nums, k):
    i, j = 0, 1
    while j < len(nums):
        if i == j:
            j += 1
            continue
        diff = nums[j] - nums[i]
        if diff == k:
            return True
        if diff < k:
            j += 1
        else:
            i += 1
    return False

print(has_pair_with_difference([1, 3, 6, 10, 15], 4))  # True (6, 10)
print(has_pair_with_difference([1, 3, 6, 10, 15], 2))  # True (1, 3)
print(has_pair_with_difference([1, 3, 6, 10, 15], 8))  # False

Problem 4. Range sum queries

Given a list of length n and q queries (l, r), return the sum of nums[l:r] for each query.

Approach: sum(nums[l:r]) per query costs O(n·q). Build prefix sums once, prefix[i] = nums[0] + ... + nums[i-1], and each query becomes a single subtraction: O(n + q) in total.

from itertools import accumulate

def range_sums(nums, queries):
    prefix = [0, *accumulate(nums)]
    return [prefix[r] - prefix[l] for l, r in queries]

print(range_sums([3, 1, 4, 1, 5, 9], [(0, 3), (2, 6), (5, 6)]))  # [8, 19, 9]

Problem 5. Estimate the exponent by measuring

Write a function that takes a function and an input generator and estimates the exponent of its growth from the times at n and 2n.

Approach: if T(n) ≈ c·n^k, then T(2n) / T(n) ≈ 2^k, so k ≈ log₂(T(2n) / T(n)). Use the minimum of timeit.repeat to reduce noise.

import math
import timeit

def estimate_exponent(func, make_input, n, number=3):
    def best_time(size):
        data = make_input(size)
        return min(timeit.repeat(lambda: func(data), number=number, repeat=5))
    return math.log2(best_time(2 * n) / best_time(n))

def all_pairs(items):
    return sum(1 for i in range(len(items)) for j in range(i + 1, len(items)))

print(round(estimate_exponent(sum, lambda n: list(range(n)), 200_000), 1))   # about 1
print(round(estimate_exponent(all_pairs, lambda n: list(range(n)), 1_000), 1))  # about 2

Summary

• Multiply loop counts, and do not miss hidden in list costs or recursive recurrences.
• Sets, two pointers and prefix sums are standard tools for turning O(n²) or O(n·q) into linear time.
• Make a habit of confirming a derived complexity with a doubling experiment.