In Module 1 we learned the language of efficiency: asymptotic notation. Now we are going to learn to use it: given a piece of real Python code, how do you work out its time complexity? In this lesson we will develop the method of line-by-line analysis: assign a cost to each operation, add up the costs of sequential lines, multiply by loop repetitions, and simplify with the rules we already know. We will apply it step by step to the functions we have already written for RutaBus, including a recursive one, and we will finish with something that surprises many developers: Python operations that look like a single step but hide a loop inside.
Two warnings before we start. First: the definitions of O, Ω and Θ were given in lesson 01-03 and here we take them as known (remember: big-O is an upper bound on the growth of the cost). Second: throughout this lesson we analyze the worst case — the input scenario that causes the most work — because it is the most common and the most prudent analysis. In lesson 02-03 we will see that the best case and the average case also exist, and when each one matters.
Contents
- The cost model: elementary operations
- Sequential code: adding costs
- Simple loops: multiplying by the repetitions
- A complete analysis of
nearest_stop - Nested loops: connectable pairs of stops
- Dependent loops: the arithmetic sum
- Function calls: the cost doesn't disappear
- Recursive functions: counting the calls
- Hidden costs of Python operations
The cost model: elementary operations
To analyze code without timing it we need an agreement: what counts as "one step"? The convention is this:
- An elementary operation is any operation whose time does not depend on the size of the input: an assignment (
x = 5), an arithmetic operation (a + b,a * b), a comparison (a < b), an access to a list position (some_list[i]), areturn. - Every elementary operation costs O(1): constant time. We don't care whether, on some particular machine, a multiplication takes twice as long as an addition — lesson 01-03 already taught us that constants are discarded.
With this model, analyzing an algorithm boils down to counting how many elementary operations are executed as a function of n (the size of the input). The result is a cost function T(n) that we then simplify to its asymptotic order.
Watch out: the key word is elementary. As we will see in the last section, Python has single-line expressions that are not elementary because they hide a full traversal. For now, let's assume we are working with the operations in the list above.
Sequential code: adding costs
The first rule of line-by-line analysis:
Rule 1 (sequence): the cost of several instructions executed one after another is the sum of their costs.
# RutaBus snippet: preparing the data for a trip
origin = "Main Square" # O(1): assignment
destination = "North Station" # O(1): assignment
ticket_price = 1.50 # O(1): assignment
total_price = ticket_price * 2 # O(1): multiplication + assignmentTotal cost: O(1) + O(1) + O(1) + O(1) = O(1). It doesn't matter whether it is 4 lines or 400: if none of them depends on n, the sum is still a constant and therefore O(1). This is the practical translation of "discarding constants" we saw in 01-03: a sequential block of elementary operations, however long, costs constant time.
Simple loops: multiplying by the repetitions
Rule 2 (loop): the cost of a loop is the cost of its body multiplied by the number of iterations.
Let's bring back count_stops_iterative from lesson 01-02:
def count_stops_iterative(stops):
counter = 0 # O(1) — executed 1 time
for _ in stops: # the loop runs n times (n = len(stops))
counter += 1 # O(1) per iteration
return counter # O(1) — executed 1 timeLet's count with n = number of stops:
| Line | Unit cost | Times executed | Total cost |
|---|---|---|---|
counter = 0 |
O(1) | 1 | O(1) |
loop body (counter += 1) |
O(1) | n | O(n) |
return counter |
O(1) | 1 | O(1) |
T(n) = O(1) + O(n) + O(1). Applying the dominant-term rule from 01-03: T(n) = O(n). Linear: if the RutaBus network doubles its stops, counting takes twice as long.
One important nuance: the number of iterations is not always exactly n. A loop for stop in stops[1:] iterates n−1 times; one that traverses half the list iterates n/2 times. Asymptotically n−1, n/2 and n are all O(n) — multiplicative and additive constants are discarded. What matters is that the number of passes grows linearly with n.
A complete analysis of nearest_stop
Let's apply the full method to the first function we wrote for RutaBus (lesson 01-01). We annotate the cost of each line as a comment:
def nearest_stop(user_x, user_y, stops):
best_stop = stops[0] # O(1): access + assignment
best_distance = distance(user_x, user_y,
best_stop["x"],
best_stop["y"]) # O(1): call to distance (see section 7)
for stop in stops[1:]: # n-1 iterations
d = distance(user_x, user_y,
stop["x"], stop["y"]) # O(1) per iteration
if d < best_distance: # O(1) per iteration
best_distance = d # O(1) per iteration (at most)
best_stop = stop # O(1) per iteration (at most)
return best_stop # O(1)Procedure:
- Before the loop: two O(1) lines → O(1) in total.
- Loop body: four O(1) operations → O(1) per iteration. (The last two only run when the comparison is true, but since we analyze the worst case we assume they always run; and even if they didn't, 2 operations versus 4 is a constant that gets discarded.)
- The loop: O(1) per iteration × (n−1) iterations = O(n).
- After the loop: O(1).
T(n) = O(1) + O(n) + O(1) = O(n). We formally confirm what in 01-01 we only sensed: finding the nearest stop with a linear scan costs linear time. For the complete network of a city (thousands of stops) it remains perfectly affordable.
Nested loops: connectable pairs of stops
Rule 3 (nesting): when a loop contains another loop, the costs are multiplied: iterations of the outer × iterations of the inner × cost of the body.
A new RutaBus requirement: the planning team wants to know which pairs of stops are close enough to be connected with a direct line segment (say, less than 2 km apart). The natural solution: compare every stop with every other one.
def connectable_pairs(stops, max_distance):
"""Returns the pairs of stops less than max_distance km apart."""
pairs = [] # O(1)
for p1 in stops: # n iterations
for p2 in stops: # n iterations FOR EACH p1
if p1["name"] < p2["name"]: # O(1): avoids duplicates and (p, p)
d = distance(p1["x"], p1["y"],
p2["x"], p2["y"]) # O(1)
if d <= max_distance: # O(1)
pairs.append((p1["name"], p2["name"])) # O(1)
return pairs # O(1)Analysis:
- The innermost body is O(1).
- The inner loop runs it n times → O(n) per pass of the outer loop.
- The outer loop makes n passes → n × O(n) = O(n²).
The comparison p1["name"] < p2["name"] is a trick to process each pair only once (it avoids examining both ("A","B") and ("B","A") as well as pairs of a stop with itself), but it does not change the order: the if is evaluated on all n² combinations even though it only succeeds on half, and n²/2 is still O(n²).
Is an O(n²) a big deal? It depends on n, and here it connects with the running-time table from 01-03: with 100 stops it is 10,000 comparisons (instantaneous); with the 10,000 stops of a metropolitan area it is 100 million (seconds). Quadratic algorithms are the first red flag a developer learns to spot: a loop inside another loop, both over the same collection.
Dependent loops: the arithmetic sum
In connectable_pairs there is an obvious waste: when p1 is stop 7, there is no need to compare it with stops 0 through 7 (they were already compared earlier, or it is the stop itself). The refined version makes the inner loop depend on the outer one:
def connectable_pairs_v2(stops, max_distance):
pairs = []
n = len(stops)
for i in range(n): # i = 0, 1, ..., n-1
for j in range(i + 1, n): # only the stops AFTER i
d = distance(stops[i]["x"], stops[i]["y"],
stops[j]["x"], stops[j]["y"])
if d <= max_distance:
pairs.append((stops[i]["name"], stops[j]["name"]))
return pairsNow the inner loop does not always make n passes: it makes n−1 when i=0, n−2 when i=1... and 0 when i=n−1. We can no longer simply multiply; we must add up the actual iterations:
This is the famous arithmetic sum, and its exact value is:
A visual trick to remember it: write the sum twice, once forwards and once backwards, and pair up the terms:
(n-1) + (n-2) + ... + 1 + 0 + 0 + 1 + ... + (n-2) + (n-1) = (n-1) + (n-1) + ... + (n-1) + (n-1) ← n pairs adding up to n-1 each
Twice the sum is n(n−1), so the sum is n(n−1)/2. Applying the simplification rules from 01-03 (discard constants like the ½, keep the dominant term n²): O(n²).
A conclusion worth internalizing: version v2 does half the actual work of v1 — a useful improvement in practice — but its order of growth is the same, O(n²). Asymptotic notation is deliberately blind to constant factors; to go from O(n²) to something better it is not enough to trim iterations, you have to change strategy (that is what Module 3 is about). This pattern — "inner loop starting where the outer one currently is → n(n−1)/2 → O(n²)" — shows up constantly: memorize it.
Function calls: the cost doesn't disappear
Rule 4 (calls): the cost of a function call is the cost of executing its body with the given arguments. Wrapping code in a function does not make it free.
In nearest_stop we cheerfully claimed that distance(...) was O(1). That has to be justified by looking at its body:
def distance(x1, y1, x2, y2):
return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) # fixed arithmetic: O(1)Subtractions, squares, one square root: a fixed number of elementary operations, independent of how many stops the network has → O(1). Correct.
But beware of this other, very typical case:
def is_transfer(stop, line_l1, line_l2):
"""Does the stop belong to both lines?"""
return has_stop_iterative(line_l1, stop) and \
has_stop_iterative(line_l2, stop)A single line, two calls... and each call to has_stop_iterative (lesson 01-02) is a linear scan: O(n). Total: O(n) + O(n) = O(n), not O(1). And if that function is called inside a loop over the n stops, the whole thing becomes O(n²). The practical rule: whenever you see a call, always ask yourself how much it costs inside — or look it up in its documentation. This will be exactly the problem of the "hidden costs" in the last section.
Recursive functions: counting the calls
For a recursive function there is no loop to multiply, but the idea is the same in a different disguise:
Cost of a recursion = (number of calls) × (cost of each call, not counting the recursive call)
Let's analyze count_stops_recursive from lesson 01-02:
def count_stops_recursive(stops):
if not stops: # O(1)
return 0 # O(1)
return 1 + count_stops_recursive(stops[1:]) # careful with stops[1:]!Step 1 — count the calls. Each call works with a list one unit shorter than the previous one. For a line with 4 stops:
count_stops_recursive([A, B, C, D]) → call 1 (size 4)
count_stops_recursive([B, C, D]) → call 2 (size 3)
count_stops_recursive([C, D]) → call 3 (size 2)
count_stops_recursive([D]) → call 4 (size 1)
count_stops_recursive([]) → call 5 (base case, size 0)For n stops: n + 1 calls. The number of calls grows linearly with n.
Step 2 — cost of each call. Here comes the surprise. The comparison and the + 1 are O(1), but stops[1:] creates a new list by copying every element except the first: if the list has k elements, the slice costs O(k) (we will confirm this in the table of the next section). So the calls cost, respectively, n, n−1, n−2, ..., 1, 0 copy operations. Does that sum ring a bell? It is the arithmetic sum again: n(n+1)/2 → O(n²).
The honest result: as written in Python, count_stops_recursive is O(n²), while its iterative sibling is O(n). If we rewrote it passing an index instead of slicing the list (avoiding the slice), each call would be O(1) and the whole recursion would be O(n), as the intuition of "n+1 constant-cost calls" dictates. A double moral: (1) the technique for recursions is to count the calls and multiply by the cost of each one; (2) in Python, that "cost of each one" can hide copies.
For richer recursions — for example a function that calls itself twice with half the problem, as merge sort will do — this handcrafted counting is formalized with the so-called recurrence equations. We don't need them yet: we will set them up and solve them for a real case in lesson 04-03 (Merge Sort). Keep the intuitive version: draw the call tree, count how many calls there are and how much each one costs.
Hidden costs of Python operations
Python is a very high-level language: a single expression can run a full loop in C underneath. For complexity analysis that is a trap: the code reads like one line but costs like a loop. This table gathers the cases that ruin the most analyses (n = size of the collection involved; all in the worst case):
| Python operation | Actual cost | Why |
|---|---|---|
some_list[i], some_list[i] = v |
O(1) | Direct access by position |
len(some_list) |
O(1) | Python stores the length, it doesn't count it |
x in some_list |
O(n) | Scans the list comparing element by element |
x in some_set, key in some_dict |
O(1)* | Hash table (*average; in 02-03 we will qualify what that means) |
some_list[a:b] (slicing) |
O(b−a) | Copies every element in the range |
some_list.append(x) |
O(1) amortized | Almost always immediate (the "amortized" is explained in 02-03) |
some_list.insert(0, x), some_list.pop(0) |
O(n) | Shifts every element one position |
s1 + s2 (strings) |
O(len(s1)+len(s2)) | Strings are immutable: a new one is created by copying both |
min(some_list), max(some_list), sum(some_list) |
O(n) | Full traversal |
sorted(some_list), some_list.sort() |
O(n log n) | Sorting (we will open it up in Module 4) |
Let's look at two of these traps in RutaBus code.
Trap 1: in over a list inside a loop. We want the stops common to two lines (possible transfers):
line_l1 = ["Main Square", "Central Hospital", "North Station", "River Park"]
line_l2 = ["Harbor Avenue", "Main Square", "University", "South Terminal"]
def transfers(line_a, line_b):
common = []
for stop in line_a: # n iterations
if stop in line_b: # O(n) EVERY TIME, not O(1)!
common.append(stop)
return commonIt looks like a simple loop → O(n), but in over a list is a hidden linear scan: n iterations × O(n) per check = O(n²). It is exactly the same nesting as in connectable_pairs, except that one of the two loops is invisible. The idiomatic fix: turn line_b into a set (stops_b = set(line_b), an O(n) cost paid once) and ask stop in stops_b, which is O(1) — the whole algorithm drops to O(n). The price is extra memory, and measuring that price is precisely the subject of the next lesson.
Trap 2: string concatenation in a loop. Generating the sign with a line's route:
def line_label(stops):
label = ""
for stop in stops:
label = label + " - " + stop # copies EVERYTHING accumulated on each pass
return labelOn pass k, label is already proportionally k characters long and the concatenation copies it in full: costs 1, 2, 3, ..., n → arithmetic sum → O(n²). The idiomatic version, " - ".join(stops), builds the result in a single step costing O(total number of characters): linear.
Common Mistakes and Tips
- Adding where you should multiply (and vice versa): instructions in sequence are added; instructions inside a loop are multiplied by the iterations. Two consecutive loops over n elements are O(n) + O(n) = O(n); a loop inside another is O(n · n) = O(n²).
- Believing that fewer lines = lower cost:
if stop in line_bis one line and costs O(n). Cost is measured in operations executed, not in lines written. For any library function or method, look up its cost (the table above covers the essentials). - Concluding O(n²/2) or O(3n): these are badly written orders. After counting, always simplify with the two rules from 01-03: constants out, non-dominant terms out. O(n²/2) is O(n²); O(3n) is O(n).
- Forgetting what n stands for: in
transfersthere are two inputs (two lines). If they have different sizes, the rigorous statement is O(a · b). We say O(n²) assuming similar sizes, but it pays to be explicit when they are not. - Ignoring the cost of slices in recursions:
f(some_list[1:])looks elegant but copies the list at every level. If the recursion has depth n, those copies add up to O(n²). Alternative: pass indices (f(some_list, i+1)). - Tip: train your eye with this mental shortcut — how many times does the innermost line of the code run? That count, simplified, is almost always the complexity of the algorithm.
Exercises
Exercise 1. Analyze the following RutaBus function line by line and give its worst-case time complexity. State how many times each line runs.
def first_and_last_arrival(schedules):
"""schedules: list of 'HH:MM' arrival times at a stop."""
first = schedules[0]
last = schedules[0]
for h in schedules:
if h < first:
first = h
for h in schedules:
if h > last:
last = h
return (first, last)Exercise 2. The RutaBus quality team wrote this function to detect duplicate stops in the network's master file. Analyze its complexity and propose an O(n) version using the Python cost table. Justify the cost of both.
def has_duplicates(stops):
for i in range(len(stops)):
for j in range(i + 1, len(stops)):
if stops[i] == stops[j]:
return True
return FalseExercise 3. Without running it, determine the complexity of this recursive function that reverses the order of a line's stops (useful for displaying the return trip). Hint: count the calls and pay attention to the cost of each call.
Solutions
Solution 1. The two initial assignments and the return are O(1) (executed 1 time). Each loop runs its body n times with O(1) cost per iteration → O(n) each. They are loops in sequence, not nested, so they are added: T(n) = O(1) + O(n) + O(n) + O(1) = O(2n) → O(n). A common mistake here: seeing two for loops and answering O(n²) — you only multiply when one is inside the other.
Solution 2. It is the dependent-loop pattern: the inner loop makes n−1, n−2, ..., 1, 0 passes → arithmetic sum n(n−1)/2 → O(n²) in the worst case (no duplicates: every pair must be checked; note that if it finds a duplicate early it finishes sooner — that difference between scenarios is precisely the subject of 02-03). Linear version with a set:
def has_duplicates_v2(stops):
seen = set()
for p in stops: # n iterations
if p in seen: # O(1): set membership
return True
seen.add(p) # O(1)
return Falsen iterations × O(1) = O(n). The price: up to O(n) of extra memory for seen — we will quantify it in lesson 02-02.
Solution 3. Calls: same as count_stops_recursive, one per size n, n−1, ..., 0 → n+1 calls. Cost of each call of size k: the slice stops[1:] costs O(k) and additionally the concatenation some_list + [x] creates a new list copying the k−1 already-reversed elements: another O(k). Total per call: O(k). Adding up k = n, n−1, ..., 1: arithmetic sum → O(n²). The iterative reversal (scanning back to front with append, or directly stops[::-1], which copies only once) is O(n).
Conclusion
We now know how to compute, and not just name, the time complexity of an algorithm. The method fits in four rules: elementary operations cost O(1); sequential code adds; loops multiply by their iterations (and when the inner loop depends on the outer one, the arithmetic sum n(n−1)/2 → O(n²) appears); and function calls cost whatever their body costs — recursive ones included, where we count calls and multiply by the cost of each one. With that method we have confirmed that nearest_stop is O(n), we have watched O(n²) being born in the connectable pairs of stops, and we have uncovered Python's hidden costs: in over lists, slices and string concatenation, capable of turning an apparent O(n) into a real O(n²). All of it, remember, measuring the worst case.
But time is only half the bill. When we replaced a list with a set to speed up transfers, or when we saw each recursive call stack up a copy of the list, we were paying with memory without accounting for it. In the next lesson (02-02) we will learn to perform exactly the same line-by-line analysis, but measuring bytes instead of steps: space complexity.