The Project | About Us | Contribute | Donations | License

HOME

Training starts here. There is no new theory in this lesson: it is a battery of exercises that works out the whole of Module 2 — time analysis (02-01), space analysis (02-02) and best/worst/average cases (02-03) — using the asymptotic notation from Module 1 (01-03). Every exercise works on code from RutaBus, our urban mobility app.

How to work through this lesson: attempt each exercise on paper before looking at the solution. Seriously. Reading a complexity-analysis solution produces the feeling of "I already knew that"; deriving it yourself is what builds the reflex. If you get stuck for more than ten minutes, read the hint (if there is one) and try again before giving up.

Deriving Θ for simple, nested and dependent loops.
Python's hidden costs: in on a list and insert(0).
Space complexity: auxiliary versus total, and recursion with slices versus indices.
Best, worst and average case of a validation function.
Matching each piece of code with its order of growth from measurements.
Spot the hidden cost: the function that looks linear but isn't.

Exercise 1: Three functions, three counts

Difficulty: basic

RutaBus stores each tap record as a tuple (time, stop, line). Analyze these three functions and derive the Θ time complexity of each as a function of n (the size of the input list). For the third one, also compute the exact number of iterations of the inner loop.

def count_line_tap_records(tap_records, line):
    total = 0
    for r in tap_records:           # n tap records
        if r[2] == line:
            total += 1
    return total

def match_matrix(stops):
    n = len(stops)
    m = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            m[i][j] = lines_match(stops[i], stops[j])  # O(1)
    return m

def conflicting_pairs(schedules):
    conflicts = []
    n = len(schedules)
    for i in range(n):
        for j in range(i + 1, n):
            if overlap(schedules[i], schedules[j]):  # O(1)
                conflicts.append((i, j))
    return conflicts

Solution

count_line_tap_records: a single loop that walks over the n tap records doing O(1) work on each pass (one comparison and, sometimes, an addition). As we saw in 02-01, the cost is proportional to the number of iterations: Θ(n). Note that the if does not change the order: whether or not the body runs, the comparison is always made.

match_matrix: two independent nested loops (the range of j does not depend on i): n · n iterations with O(1) work each. The prior creation of the matrix also costs Θ(n²), but it does not change the total: Θ(n²).

conflicting_pairs: here the inner loop depends on i. Let's count the exact iterations: for i = 0 there are n−1, for i = 1 there are n−2, …, for i = n−1 there are 0. The sum is:

(n−1) + (n−2) + … + 1 + 0 = n(n−1)/2

As we saw in 02-01, n(n−1)/2 = n²/2 − n/2, and when simplifying (01-03) we drop constants and lower-order terms: Θ(n²). The dependent loop does half the work of the independent one, but half of a quadratic is still quadratic.

Common mistakes: (1) thinking the dependent loop is "something in between" like O(n log n) — no: the arithmetic series gives quadratic; (2) adding Θ(n²) + Θ(n²) for the matrix creation and saying Θ(2n²) — constants are dropped.

Exercise 2: The price of `in` and `insert(0)`

Difficulty: medium

The RutaBus data team wrote these two functions. Derive their real time cost. Call n the number of tap records/alerts, m the size of known_stops and k the number of new stops found.

def new_stops(tap_records, known_stops):
    # known_stops is a LIST of m names
    new_ones = []
    for time, stop, line in tap_records:       # n iterations
        if stop not in known_stops:            # cost?
            if stop not in new_ones:           # cost?
                new_ones.append(stop)
    return new_ones

def latest_first(alerts):
    result = []
    for alert in alerts:             # n iterations
        result.insert(0, alert)      # cost?
    return result

Questions: (a) what is the cost of each marked check?; (b) what is the total cost of each function?; (c) what happens to new_stops in the worst case where all the stops are new?

Hint: review the hidden-costs table from 02-01: x in a_list does not cost the same as x in a_set, and Python lists are optimized for touching their end, not their beginning.

Solution

(a) As we saw in 02-01, stop not in known_stops on a list is a linear search: O(m). The second check, stop not in new_ones, costs O(k) where k is the current size of new_ones. And result.insert(0, alert) shifts every existing element one position: O(current length).

(b) new_stops does n iterations and pays O(m) + O(k) on each: total O(n·(m + k)). latest_first pays 0 + 1 + 2 + … + (n−1) = n(n−1)/2 shifts: Θ(n²) — the same arithmetic series as in Exercise 1, this time hidden inside a method.

(c) If all the stops are new, k grows up to n and the cost becomes O(n·m + n²): the function that "looked like" a linear filter is quadratic.

For the record (the repair is practiced in 06-03, here we only diagnose): the check would be O(1) with a set, and latest_first would be Θ(n) with append + reverse() (or directly alerts[::-1]).

Common mistake: counting each line of Python as "one operation". The line if stop not in known_stops: is one line, but it is m comparisons. The line-by-line analysis from 02-01 requires knowing the real cost of each operation, not its typographic length.

Exercise 3: Auxiliary space, total space and the stack

Difficulty: medium

Two recursive versions of the occupancy sum for a trip (list of passengers per segment):

def occupancy_sum_slice(occupancy):
    if not occupancy:
        return 0
    return occupancy[0] + occupancy_sum_slice(occupancy[1:])

def occupancy_sum_indices(occupancy, i=0):
    if i == len(occupancy):
        return 0
    return occupancy[i] + occupancy_sum_indices(occupancy, i + 1)

Questions: (a) auxiliary space of each version; (b) total space; (c) time complexity of each; (d) what happens in practice when calling them with a list of 10,000 segments?

Solution

(a) Auxiliary space. Both versions make n+1 nested calls, so both pay a stack of depth Θ(n) (02-02: each stack frame counts as auxiliary space). But the slice version additionally pays one copy per call: occupancy[1:] creates a new list of n−1 elements, the next call creates another of n−2, and so on. And here is the important part: while the recursion is at its deepest point, all those copies are alive at the same time (each one is an argument of a frame that has not yet returned). Total: (n−1) + (n−2) + … + 1 ≈ n²/2 → auxiliary space Θ(n²). The index version copies nothing: only the stack, Θ(n) auxiliary.

(b) Total space = input + auxiliary (02-02). With slices: Θ(n) + Θ(n²) = Θ(n²). With indices: Θ(n) + Θ(n) = Θ(n).

(c) Time. The slice does not just take up space: it also takes O(length) time to copy (02-01). The slice version pays the same arithmetic series in time: Θ(n²). The index version: Θ(n).

(d) Neither of the two survives 10,000 elements: Python limits recursion depth to ~1000 by default, so both raise RecursionError well before memory becomes the problem. As we saw in 01-02 when comparing iterative and recursive, when the recursion is purely linear, a loop (or sum(occupancy)) does the same work with an O(1) stack.

Common mistakes: (1) forgetting that the slice copies (it looks like an access, but it is a new list); (2) counting only "one stack frame" instead of the maximum simultaneous depth; (3) confusing auxiliary space with total and reporting Θ(n²) for the index version "because the input plus the stack add up to a lot" — the input is Θ(n) and the stack Θ(n): total Θ(n).

Exercise 4: Best, worst and average in ticket validation

Difficulty: medium

On each tap, RutaBus validates the ticket against the list of active tickets:

def validate_tap_record(ticket, active_tickets):
    # active_tickets: list of n identifiers
    for active in active_tickets:
        if active == ticket:
            return True
    return False

Operational data says that 90% of taps are valid, and that valid tickets appear at uniformly distributed positions in the list. The remaining 10% are invalid tickets (not in the list).

Questions: (a) best case and worst case, with the appropriate notation; (b) expected number of comparisons under that distribution, and the Θ of the average case; (c) if the percentage of invalid tickets rose to 99%, would the Θ of the average change?

Solution

(a) Best case: the ticket is the first in the list → 1 comparison → Θ(1). Worst case: the ticket is last or not present → n comparisons → Θ(n). Note that we use Θ of the case, as we made precise in 02-03: each case has its own tight bound.

(b) It is exactly the linear-search scheme from 02-03, but with the given distribution. If the ticket is valid and at a uniform position, the average number of comparisons is (1 + 2 + … + n)/n = (n+1)/2. If it is invalid, it is always n. Total expectation:

E[comparisons] = 0.9 · (n+1)/2 + 0.1 · n = 0.45n + 0.45 + 0.1n = 0.55n + 0.45

That is Θ(n): a straight line with slope 0.55, but a straight line all the same.

(c) With 99% invalid: E = 0.01 · (n+1)/2 + 0.99 · n ≈ 0.995n. The constant almost doubles compared with the previous case (0.55 → 0.995), which is noticeable in production, but the Θ does not change: it is still Θ(n). This is the lesson of 02-03: the input distribution moves the constants of the average, and only sometimes moves the order.

Common mistake: writing "the average is Θ(n/2), which is better than Θ(n)". Θ(n/2) is Θ(n) — asymptotic notation does not distinguish constants (01-03). If you want to communicate the constant, say "≈ 0.55n comparisons"; don't invent a new Θ.

Exercise 5: Match the code with its curve

Difficulty: medium

The RutaBus team measured four functions (F1–F4) with inputs of increasing size and got these times (milliseconds):

n	F1	F2	F3	F4
1,000	0.8	0.0004	90	0.0011
2,000	1.6	0.0004	360	0.0012
4,000	3.2	0.0004	1,440	0.0013

And these are the four pieces of code, without saying which is which:

def A(times, i, j):                   # times: matrix of minutes between stops
    return times[i][j]

def B(departures, time):              # departures: SORTED list of times
    lo, hi = 0, len(departures)
    while lo < hi:
        mid = (lo + hi) // 2
        if departures[mid] < time:
            lo = mid + 1
        else:
            hi = mid
    return lo

def C(occupancy):
    return sum(occupancy) / len(occupancy)

def D(stops):
    nearby = 0
    for i in range(len(stops)):
        for j in range(i + 1, len(stops)):
            if distance(stops[i], stops[j]) < 500:
                nearby += 1
    return nearby

Match A, B, C and D with F1, F2, F3 and F4, reasoning from how the time scales when n doubles, and assign each one its Θ.

Hint: when n doubles, a Θ(n) doubles its time, a Θ(n²) quadruples it, a Θ(log n) adds a tiny fixed amount and a Θ(1) doesn't flinch. It's the hierarchy from 01-03 seen from the stopwatch.

Solution

We apply the doubling heuristic:

F1: 0.8 → 1.6 → 3.2. It doubles when n doubles: linear growth, Θ(n). It is C, which walks over the list once to sum it.
F2: constant, always 0.0004: Θ(1). It is A: an indexed matrix access does not depend on n.
F3: 90 → 360 → 1,440. It quadruples when doubling: Θ(n²). It is D, the dependent loop over pairs (n(n−1)/2 iterations, Exercise 1).
F4: 0.0011 → 0.0012 → 0.0013. It adds a tiny fixed amount when n doubles: Θ(log n). It is B: each pass of the while halves the interval, so there are ~log₂ n passes.

Function	Code	Θ	Signal in the table
F1	C	Θ(n)	×2 when n doubles
F2	A	Θ(1)	no change
F3	D	Θ(n²)	×4 when n doubles
F4	B	Θ(log n)	+constant when n doubles

Common mistakes: (1) comparing absolute values across columns ("F3 is the slowest, so it's the worst function") — what matters is how it scales, not what it is worth at one specific n: for small n a Θ(n²) can beat a Θ(n) with a large constant; (2) confusing Θ(log n) with Θ(1) because "it barely grows" — it grows, and the difference matters when n has nine digits.

Exercise 6: Spot the hidden cost

Difficulty: high

This function generates the network's daily incident report. Its author claims that "it's a single loop, so it's O(n)". Your job: (a) state the real complexity; (b) point out every hidden cost with its line and its individual cost; (c) justify the total. No need to fix it (that is 06-03 material): just diagnose it precisely.

def incident_report(incidents):
    # incidents: list of n strings "time;line;text"
    report = ""
    processed = []
    for inc in incidents:
        time, line, text = inc.split(";")
        if inc in processed:                            # line A
            continue
        processed.append(inc)
        report = report + line + " " + time + "\n"      # line B
    return report

Solution

(a) The real complexity is Θ(n²), not Θ(n).

(b) There are two hidden costs, both seen in 02-01:

Line A — inc in processed: a linear search over a growing list. On iteration i, processed has up to i elements, so the check costs O(i). Summing: 0 + 1 + … + (n−1) = n(n−1)/2 → Θ(n²) for this line alone.
Line B — report = report + ...: Python strings are immutable; each concatenation creates a new string copying everything before it. If the report ends up with L characters, the accumulated cost of rebuilding it piece by piece is Θ(L²) — and L is proportional to n, so also Θ(n²).

(The split(";") on each line is O(length of the string), which we treat as constant if the incidents have bounded size — this is not a problematic hidden cost.)

(c) Total: Θ(n²) + Θ(n²) = Θ(n²). The "one loop, therefore O(n)" fails because line-by-line analysis requires the cost of each internal operation, and here two innocent-looking operations (an in and a +) hide full traversals of structures that grow with n.

Common mistake: spotting one of the two costs and calling the analysis done. In real code hidden costs come in groups, because the same programming style (accumulating onto a list/string and querying with in) produces them all at once. Get used to auditing every operation in the loop body.

Conclusion

You have exercised the full analysis cycle of Module 2: deriving Θ by counting iterations (simple, nested and dependent loops with their n(n−1)/2), unmasking Python's hidden costs (in on a list, insert(0), slices that copy, string concatenation), distinguishing auxiliary from total space (recursion stack included), separating best/worst/average with concrete distributions, and reading orders of growth straight off a table of measurements with the doubling heuristic.

If any exercise resisted you, go back to the corresponding lesson (02-01 for time and hidden costs, 02-02 for space, 02-03 for cases) and retry it tomorrow: complexity analysis is one of those skills that consolidates on the second pass. In the next lesson we switch muscles: from analyzing given code to designing new algorithms with the four strategies of Module 3.

Time and Space Complexity Exercises

Contents

Exercise 1: Three functions, three counts

Solution

Exercise 2: The price of `in` and `insert(0)`

Solution

Exercise 3: Auxiliary space, total space and the stack

Solution

Exercise 4: Best, worst and average in ticket validation

Solution

Exercise 5: Match the code with its curve

Solution

Exercise 6: Spot the hidden cost

Solution

Conclusion

Algorithm Analysis and Design Course

Module 1: Introduction to Algorithms

Module 2: Algorithm Analysis

Module 3: Algorithm Design Strategies

Module 4: Classic Algorithms

Module 5: Algorithm Optimization

Module 6: Practice and Exercises

Time and Space Complexity Exercises

Contents

Exercise 1: Three functions, three counts

Solution

Exercise 2: The price of in and insert(0)

Solution

Exercise 3: Auxiliary space, total space and the stack

Solution

Exercise 4: Best, worst and average in ticket validation

Solution

Exercise 5: Match the code with its curve

Solution

Exercise 6: Spot the hidden cost

Solution

Conclusion

Algorithm Analysis and Design Course

Module 1: Introduction to Algorithms

Module 2: Algorithm Analysis

Module 3: Algorithm Design Strategies

Module 4: Classic Algorithms

Module 5: Algorithm Optimization

Module 6: Practice and Exercises

Exercise 2: The price of `in` and `insert(0)`