Exercise: Analyzing Time Complexity

Build the mental model

Reading code for complexity is a repeatable procedure, not guesswork. Start by counting loop nesting: a single pass over n items is O(n); a loop nested inside another, both scaling with n, multiplies to O(n²) — but only if the inner bound actually depends on n. A loop that always runs a fixed number of times (say, 26 or 10) contributes a constant factor, not a variable one, and gets dropped. Next, look for halving patterns: any loop or recursive call that divides the remaining problem by a constant factor each step (binary search, balanced-tree descent) is O(log n), since the number of steps to shrink n to 1 is log₂n. Then classify individual operations: dict/set membership and lookup are O(1) on average due to hashing; arithmetic and comparisons are O(1); but list.insert(0, x), list.pop(0), linear search with `in` on a list, and repeated string concatenation with `+=` inside a loop are each O(n) because they shift or rescan the whole structure. Finally, combine pieces correctly — statements that run one after another in sequence *add* their costs (which simplifies to the largest term), while statements nested inside a loop *multiply*. Always drop constants and lower-order terms; only the dominant term as n grows matters.

Connect it to a real scenario

Picture Tutorial Platform engineers reviewing the "related lessons" feature's code. If a function compares every lesson against every other lesson to find similarity, you should be able to spot from the code alone that it's O(n²) — fine at 50 lessons, a production timeout waiting to happen at 50,000. Reading time complexity fluently is exactly the audit skill engineers need to catch scaling bottlenecks in a design before they become an incident, rather than after.

Count loop nesting — multiply only when the inner bound depends on n; drop fixed-count loops as constants.
Recognize halving patterns (binary search etc.) as O(log n); dict/set lookup as O(1); list.insert(0,x) and linear search as O(n).
Add costs for sequential code and keep the dominant term; multiply costs for nested code.

Try the working example

python

# Snippet A
def sum_all(items):
    total = 0
    for x in items:          # single loop over n items
        total += x
    return total

# Snippet B
def has_duplicate_pair(items):
    n = len(items)
    for i in range(n):       # outer loop over n
        for j in range(n):   # inner loop also over n
            if i != j and items[i] == items[j]:
                return True
    return False

# Snippet C
def count_seen(items, seen_set):
    count = 0
    for x in items:          # loop over n
        if x in seen_set:    # set membership is O(1) average
            count += 1
    return count

# Snippet D
def binary_search(sorted_items, target):
    lo, hi = 0, len(sorted_items) - 1
    while lo <= hi:           # search space halves each iteration
        mid = (lo + hi) // 2
        if sorted_items[mid] == target:
            return mid
        elif sorted_items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

You should see

The correct classification is Snippet A = O(n), Snippet B = O(n²), Snippet C = O(n) (the set lookup is O(1), so the single loop dominates), and Snippet D = O(log n).

5-minute try-it

State the Big-O of all four snippets, and for each one write one sentence of reasoning citing loop nesting, the underlying operation's cost, or the halving pattern involved.

One important caution

Assuming any loop containing an 'if' or lookup must be O(n²) — this comes from pattern-matching on loop shape instead of checking the actual cost of the operation inside the loop, which here is O(1) set membership.

Assuming every nested loop is O(n²) without checking whether the inner loop's bound actually depends on n — a nested loop with a fixed, constant range contributes only a constant factor, not another n term.

Python Wiki — Time Complexity — Data Structures & Algorithms