Big-O in Practice — Counting, Not Vibes

Review boundary and corrected contracts

Count operation costs and distinguish upper bounds from tight growth. Sorting has O(n log n) worst-case comparison complexity but can be linear on existing runs. Slicing allocates; hash lookup bounds assume suitable keys and collision behavior.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Learn to count the cost of an algorithm by counting operations, and to derive the cost of each Python built-in from how it is implemented — so complexity becomes reasoning, not recall.

Series: LeetCode — From Basics to Production-Ready · Session 2 / 65 · Phase 0 · Foundations

Prerequisites: L01 (the constraint → complexity budget). This session gives you the tool to justify the budget instead of memorising it.

What this session IS — counting operations

Big-O is an asymptotic upper bound, not a stopwatch or necessarily a tight growth rate. A function is O(g(n)) when it is eventually at most a constant times g(n). Θ(g(n)) additionally gives a matching lower bound. Thus a linear function is both O(n) and O(n²), but Θ(n), not Θ(n²). Doubling ratios can suggest a model; a finite timing experiment does not prove an asymptotic bound.

The naive way people "learn" this is to memorise a table: "dict lookup is O(1), list .index() is O(n)…" Then under pressure they blank, or worse, guess wrong. The reliable way — the one this session teaches — is to count the operations by asking "how is this thing built, and how much work does one call do?" A derivation makes assumptions visible; still check implementation-sensitive operations against the relevant runtime documentation.

Real: A recipe that says "stir once per guest" scales linearly with guests. A recipe that says "introduce every guest to every other guest" scales with guests squared — 10 guests is 45 introductions, 100 guests is 4,950.

A full n-iteration loop with constant-cost work is Θ(n). Two full independent
n-iteration loops nested together do Θ(n²) work. Other nested loops may
have dependent bounds or shared progress: count total iterations, not indentation.

Why "vibes" fail

Ask someone the cost of if x in my_list versus if x in my_set. By vibes both look like one line. By counting: in on a list checks each element until it finds x — up to n comparisons, O(n). in on a set hashes x and probes for an equal key — expected O(1) under suitable hashing and bounded-cost keys, but O(n) in a collision-heavy worst case. Equality and hashing can themselves be expensive. The asymptotic distinction does not imply a fixed speed ratio.

The counting rules

To find the Big-O of a block of code, apply these mechanically:

1. Name the cost model: bounded-size arithmetic and simple reference work may be O(1).
   Large integers, strings, custom equality and destructor work need separate costs.
2. A loop that runs n times = multiply its body's cost by n.
3. For independent rectangular loops, multiply counts (n*m).
   Otherwise sum the actual inner work over outer iterations.
4. Sequential blocks = ADD, then keep the biggest (O(n) + O(n^2) = O(n^2)).
5. Drop constants and lower terms (3n + 5 -> O(n); n^2 + n -> O(n^2)).
6. A call to a built-in = look up (or derive) ITS cost and substitute it.

Rule 6 is where people trip: sorting an n-item list costs O(n log n) comparisons in the worst case, not one operation. Repeatedly sorting an unchanged sorted list can exploit its existing run, so this upper bound need not be tight for that particular loop.

Why keep the dominant term? For n >= 1, 5n² + 100n + 3000 lies between 5n² and 3105n², proving Θ(n²). The constants matter to actual runtime, but not to this eventual growth class. Small n can still be expensive if constants or per-operation work are large.

Use summation when nesting is not rectangular: for i in range(n): for j in range(i): ... executes n(n-1)/2 bodies. A pointer that only advances across the array can move at most n times across all inner-loop calls; an outer loop plus such a shrink loop can remain Θ(n). Conversely, one loop that repeatedly copies a growing prefix can be quadratic. For independent input sizes n and m, retain both: O(n+m) cannot generally be shortened to O(n).

The Python cost table — and how each row is derived

These are CPython-oriented costs with bounded-cost comparisons/hashes and ordinary containers. Distinguish average, amortized and worst-case claims; another Python implementation need not use identical internals:

Repeated front removals shift list references; repeated membership scans revisit elements; repeated string copies can revisit a growing prefix. Consider deque, a set and "".join respectively, but first verify their input and ordering contracts. “In place” sorting means the same list object is modified, not that sorting uses O(1) temporary memory. CPython sorting can use O(n) auxiliary storage. A key function also runs once per element and its cost must be counted.

The template — annotating a function's cost

Here is the mechanical procedure applied to a real snippet. Read the comments as the counting.

def has_duplicate_slow(nums):        # nums has length n
    for i in range(len(nums)):       # outer loop: runs n times
        for j in range(len(nums)):   # inner loop: runs n times  -> n * n
            if i != j and nums[i] == nums[j]:  # O(1) body
                return True
    return False
# Cost: n * n * O(1) = O(n^2). Two nested loops over n -> square it.
 
def has_duplicate_fast(nums):        # nums has length n
    seen = set()                     # O(1)
    for x in nums:                   # loop runs n times
        if x in seen:                # set membership: O(1) average
            return True
        seen.add(x)                  # O(1) average
    return False
# Expected cost: n * O(1) = O(n), assuming suitable bounded-cost hashable values.

For bounded hashable values, the no-duplicate case makes the scan quadratic, whereas the set version is expected-linear. Both can return early; the hash version also uses O(n) extra storage and depends on the hash/equality contract.

Name: Multiply down, add across, keep the biggest

Picture: Read the code top to bottom. Each loop is a multiplier stacked on its body. Sibling blocks are added. Then you erase everything except the fastest-growing term and its shape.

• Independent nested counts multiply; dependent counts require a sum or amortized argument.

• Sequence adds (block after block = sum, keep the max).

• A built-in call substitutes ITS cost, not O(1) by default.

• Strip constants and lower terms at the very end.

Trigger: Any time you want the complexity of code you wrote: point at each loop and each built-in and say its cost out loud, then combine.

Memory technique — the "loops and lookups" chant

Ask two questions: how much work does each operation do, and how many times can it happen in the whole algorithm? Include recursion, output construction, slices and key creation—not just visible loops.

Misconception: one line means constant cost. A comprehension that calls an O(n) helper n times is O(n²), while sum(range(n)) still processes n integers despite its short spelling. A full visit to n items is an Ω(n) lower bound in the per-item model, not a proof of an O(n) upper bound. State both bounds when claiming Θ(n).

What reviewers actually ask

Complexity analysis is not its own problem set — it is the sentence you must produce after every solution. But these classic problems are where a wrong cost read sinks people:

• Contains Duplicate (217) · Practice selection. (Easy) — probes: do you know x in list is O(n), making the naive check O(n^2), and that a suitable set gives expected O(n). Follow-up: "what if only constant workspace is allowed?" (an in-place heapsort plus scan is possible; Python list.sort has linear worst-case workspace).
• Two Sum (1) · Practice selection. (Easy) — probes: can you state the O(n^2) brute cost and the expected O(n) hash cost correctly. Follow-up: sorted input → two pointers, O(1) space.
• Valid Anagram (242) · Practice selection. (Easy) — probes: O(n) count-compare vs O(n log n) sort-and-compare, and which you would pick and why.
• Group Anagrams (49) · Practice selection. (Medium) — probes: cost of the key you choose (sorted string is O(k log k) per word) and how it multiplies over n words.
• Top K Frequent Elements (347) · Practice selection. (Medium) — for n inputs, u distinct values and 1 <= k <= u, count first in expected O(n), then compare a size-k heap (O(u log(k+1))), full frequency sort (O(u log u)) and n frequency buckets (O(n+u)). Include counting and output costs in each total.
• Merge Intervals (56) · Practice selection. (Medium) — probes: recognising the O(n log n) sort dominates the O(n) merge, so the whole thing is O(n log n).

Worked example 1 — the hidden quadratic

Problem in plain words: Given a list, return True if any value appears twice.

Brute + cost. if nums[i] in nums[i+1:] makes a suffix copy before scanning it. With all values distinct, the copied lengths sum to n(n-1)/2: Θ(n²) total work, with O(n) peak temporary space for one slice. An explicit index-pair loop avoids slices and uses O(1) auxiliary space, but still takes quadratic worst-case time.

Insight. Before the current item, seen contains exactly the preceding distinct values. Membership therefore detects a repeated value, provided values are hashable and equality/hash behavior is consistent. Ordinary integer-key set operations give expected constant-time membership.

def contains_duplicate(nums):
    seen = set()                 # O(1)
    for x in nums:               # n iterations
        if x in seen:            # O(1) average  <-- the fix
            return True
        seen.add(x)              # O(1) average
    return False
# Expected time O(n), space O(n), for bounded-cost suitably hashed values.

Complexity. Expected O(n) time and O(n) auxiliary space for the set; worst-case collision behavior can make time O(n²). Compare with the slice version’s O(n²) time/O(n) peak space and the explicit pair scan’s O(n²) time/O(1) space. These are different baselines, not interchangeable “naive” implementations.

Follow-up. With mutation permitted, sorting then scanning neighbors gives O(n log n) worst-case comparison time. Python’s list.sort can require O(n) auxiliary memory despite modifying the list in place. To meet a strict O(1)-workspace contract, choose and analyze an algorithm such as in-place heapsort; changing the API call’s name is not a space proof.

Bounded experiment: count copied elements and time the actual slice version on no-duplicate inputs. Run after contains_duplicate.

from timeit import repeat
 
def slow(nums):
    for i in range(len(nums)):
        if nums[i] in nums[i+1:]:
            return True
    return False
 
for n in (150, 300, 600):
    nums = list(range(n))
    assert slow(nums) == contains_duplicate(nums) == False
    print("n", n, "copied references", n * (n - 1) // 2)
    for fn in (slow, contains_duplicate):
        print(fn.__name__, min(repeat(lambda: fn(nums), number=3, repeat=3)) / 3)

The copy counts approximately quadruple on doubling; set insertions double. Elapsed times need not follow exact ratios at these small sizes. These timings exclude input construction and use timeit’s default cyclic-GC behavior; they do not predict a judge timeout.

Worked example 2 — where the sort dominates

Problem in plain words: Given mutable two-item lists describing closed intervals [start, end] with start <= end, merge overlaps, including touching endpoints. Mutation is allowed: the function sorts the outer list and may extend the first sorted interval in place. Its first output interval aliases that input interval; later output intervals are newly allocated. Use copied input if the caller requires preservation.

Brute idea. Repeated pairwise merging can rescan many intervals. Sorting once supports a precise bound rather than an unexplained repeated search.

Invariant. After a sorted prefix, merged is its union as disjoint, start-ordered intervals. A next start greater than the last merged end cannot overlap any earlier block. Otherwise it overlaps the last block, whose end becomes the larger end. Sorting by start makes these cases exhaustive. For half-open intervals, touching endpoints would require a different overlap convention.

def merge(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda iv: iv[0])   # O(n log n) worst-case comparisons; adaptive on runs
    merged = [intervals[0]]
    for start, end in intervals[1:]:       # O(n) pass
        last = merged[-1]
        if start <= last[1]:               # overlaps the current block
            last[1] = max(last[1], end)    # extend it
        else:
            merged.append([start, end])    # gap -> start a new block
    return merged

Complexity. Worst-case O(n log n) comparisons for sorting plus O(n) merging under bounded-cost endpoints. Existing runs can reduce sorting work. Output is O(n), and auxiliary space is O(n) even excluding output: CPython sorting can allocate a linear buffer, and intervals[1:] creates a linear slice. Permission to mutate does not remove either allocation.

Follow-up. "Insert one new interval into an already-sorted list (57)." → no sort needed, single O(n) pass; the dominant term drops to O(n) because you removed the sort.

Decision: Set/dict for O(1) lookups, or sort for O(n log n) ordering?

Name: Hash (set/dict)

Gain: O(1) average lookups; turns many O(n^2) scans into O(n).

Cost: O(n) extra memory; no key-sorted order; O(1) is expected, not worst case. Dictionaries retain insertion order, which is different from sorting by key.

Pick: Membership, counting, complement lookups where order does not matter.

Name: Sort first

Gain: Enables two-pointers, adjacency and binary search; workspace depends on the sorting algorithm, not merely whether its API mutates the input.

Cost: O(n log n) up front; mutates or copies the input.

Pick: When adjacency or order unlocks a linear pass; check actual sorting workspace if memory is tight.

Name: Neither (plain scan)

Gain: Zero extra memory, dead simple.

Cost: Often O(n^2) when it hides a membership test in a loop.

Pick: A one-off scan is sufficient or additional indexing would not repay its construction and memory costs; a single full scan can be optimal even for large input.

Verdict: Match the representation to the contract. Hashing can remove repeated membership scans for suitable keys; sorting can make adjacency useful. Neither is a universal replacement when key semantics, ordering or space requirements differ.

Where this shows up in production

A hypothetical regression is membership against a growing list inside a processing loop: tiny tests hide quadratic work. A set can help when values are hashable, duplicates need not be retained and expected lookup behavior is acceptable. It is not always a drop-in replacement: unhashable lists, custom equality, ordering requirements or memory limits may call for a different design. Profile representative data and preserve semantics rather than claiming every slowdown has the same fix.

You can now…

• Find a code block's Big-O by counting loops and substituting built-in costs.

• Sum dependent-loop work, multiply independent bounds, add sequential blocks and distinguish O from Θ.

• Recite why each Python built-in costs what it does (list vs set vs heap vs deque).

• Spot an accidental O(n^2): a membership test or slice inside a loop.

• Identify the dominating line (e.g. the sort) in a multi-step function.

• State time AND space complexity out loud after solving.

Self-check (answer follows each question).

Recall check

Q: What is the cost of x in my\_list and how does it change inside a loop over n items?

A: O(n) worst-case bounded-cost comparisons per membership call; n full scans can make Θ(n²). Successful early matches can be cheaper.

Q: A function sorts (O(n log n)) then does a single pass (O(n)). Overall complexity?

A: O(n log n) — sequential blocks add, keep the biggest term.

Q: Why can repeated growing-string concatenation be quadratic?

A: If each of n bounded-size additions copies the accumulated prefix, the copied lengths sum to Θ(n²). Some implementations optimize particular += cases, so immutability alone does not prove every run copies. join is the portable linear-in-total-output-length construction for an existing sequence of string parts.

Q: Which Python structure gives O(1) at BOTH ends, and which list operation is secretly O(n)?

A: collections.deque is O(1) at both ends; list.pop(0)/insert(0, x) is O(n) because elements shift.

Q: Turn 5n^2 + 100n + 3000 into Big-O.

A: O(n^2) — keep the fastest-growing term, drop constants and lower terms.

Q: ★ You have for x in nums: if target - x in seen: .... What must seen be to keep this O(n), and what breaks if it is a list?

A: A set/dict with bounded-cost suitable hashes gives expected O(1) membership and expected O(n) total work. List membership can yield O(n²) worst-case work. Other bounded-universe structures can also support constant-time membership; a set is not the only possible representation.

Practice queue

Solve, then state both time and space complexity out loud — with the reason.

• Contains Duplicate (217) — Easy · list-in vs set-in. (spaced-repeat anchor: +7d)
• Valid Anagram (242) — Easy · O(n) count vs O(n log n) sort.
• Two Sum (1) — Easy · state brute O(n^2) then hash O(n).
• Group Anagrams (49) — Medium · cost of the key you choose.
• Top K Frequent Elements (347) — Medium · heap vs sort vs bucket. (spaced-repeat anchor: +21d)
• Merge Intervals (56) — Medium · the sort dominates.
• Product of Array Except Self (238) — Medium · O(n) with prefix/suffix, no division.

Next session (L03) develops Counter, defaultdict, heapq and comprehensions. Short code still needs a contract and a cost argument.

Corrective source notes

• CPython v3.14.0 sorting design — adaptive natural mergesort and a temporary array of up to N//2 pointers; inspected 2026-10-09. This is an implementation-specific memory statement, not a guarantee for every Python runtime.
• Python 3.14 timeit — repeated callable measurements and GC boundary; inspected 2026-10-09.
• Python FAQ: efficient string concatenation — general quadratic repeated concatenation and the join idiom; inspected 2026-10-09.
• PEP 8 programming recommendations — CPython’s in-place concatenation optimization is fragile and not portable; inspected 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.