L02 · Big-O in Practice — Counting, Not Vibes

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

What this session IS — counting operations

Big-O is not a stopwatch. It does not say "this takes 3 seconds." It says how the work grows as the input grows. If doubling the input roughly doubles the work, that is O(n). If doubling the input quadruples the work, that is O(n^2). If doubling the input adds only a constant sliver, that is O(log n).

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?" Once you can derive the cost, you never have to trust your memory.

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 jumps straight to its bucket — O(1) average. Same syntax, hundred-thousand-fold difference at scale. Vibes cannot see that; counting can.

The counting rules

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

1. A single statement (assignment, arithmetic, comparison) = O(1).
2. A loop that runs n times = multiply its body's cost by n.
3. Nested loops = multiply their counts (n * n = n^2, n * m = n*m).
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: list.sort() inside a loop is not "one line," it is O(n log n) per iteration.

The Python cost table — and how each row is derived

Memorising this is fine, but derive it once so you can rebuild it cold:

The killers, learned the hard way, are the O(n) operations that look free: list.pop(0), x in list, and str += in a loop. Reach for deque, a set, and "".join respectively.

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
# Cost: n * O(1) = O(n). One pass, O(1) per step.

Same problem, O(n^2) versus O(n), decided entirely by "is the inner check a scan or a hash?" — rule 6 in action.

Memory technique — the "loops and lookups" chant

Two questions recover almost every complexity you will meet in interviews:

1. "How many loops, and are they nested?" → gives you the n, n^2, n^3 skeleton.
2. "What's inside — a scan or a lookup?" → a set/dict lookup keeps the body O(1); an in list or .index() secretly multiplies by another n.

Chant it: "Count the loops, then check the lookups." The loops set the exponent; a hidden linear lookup bumps that exponent up by one. If you catch yourself writing something in a_list inside a loop, a bell should ring: that is an accidental n^2.

What interviewers 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) · Amazon, Adobe (Easy) — probes: do you know x in list is O(n), making the naive check O(n^2), and that a set fixes it to O(n). Follow-up: "what if you cannot use extra space?" (sort → O(n log n)).
• Two Sum (1) · Amazon, Google, Meta (Easy) — probes: can you state the O(n^2) brute cost and the O(n) hash cost correctly. Follow-up: sorted input → two pointers, O(1) space.
• Valid Anagram (242) · Amazon, Bloomberg (Easy) — probes: O(n) count-compare vs O(n log n) sort-and-compare, and which you would pick and why.
• Group Anagrams (49) · Amazon, Uber (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) · Amazon, Meta (Medium) — probes: heap O(n log k) vs full sort O(n log n) vs bucket O(n) — a pure complexity-tradeoff conversation.
• Merge Intervals (56) · Amazon, Meta, Google (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. "For each element, is it in the rest of the list?" People write if nums[i] in nums[i+1:]. That inner in is O(n) and slicing copies — this is O(n^2) hiding as one clean line. At n = 10^5 it dies.

Insight. Replace the linear membership test with a constant-time one: a set. This is the "check the lookups" bell ringing.

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
# Time O(n), space O(n).

Complexity. O(n) time, O(n) space — versus O(n^2) time, O(1) space for the naive. Classic memory-for-time trade.

Follow-up. "No extra memory allowed." → sort in place, then scan neighbours: O(n log n) time, O(1) extra space. You traded time budget back for the space budget — name that out loud.

import random, time
nums = list(range(30000))                 # all unique -> worst case, no early exit
random.shuffle(nums)
 
def slow(nums):
    for i in range(len(nums)):
        if nums[i] in nums[i+1:]:          # O(n) membership + slice copy = O(n^2)
            return True
    return False
 
t = time.time(); slow(nums); print("slow", round(time.time()-t, 3), "s")
t = time.time(); contains_duplicate(nums); print("fast", round(time.time()-t, 3), "s")

Worked example 2 — where the sort dominates

Problem in plain words: Given intervals like [1,3], [2,6], [8,10], merge all overlapping ones.

Brute idea. Compare every interval to every other repeatedly — O(n^2) or worse. Reading the constraints (n up to 10^4) says n^2 is borderline; there is a cleaner O(n log n).

Insight. If you sort by start, overlaps become adjacent, so one linear pass merges them.

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])   # O(n log n) -- this DOMINATES the whole function
    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. Sort O(n log n) + merge O(n) = O(n log n) (rule 4: add, keep the biggest). Space O(n) for output, or O(1) extra if you may mutate. The whole point of the counting rules: you can say which line dominates.

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.

Where this shows up in production

The "hidden O(n) lookup inside a loop" bug is one of the most common real performance regressions. A function that checks membership against a growing Python list works fine in tests with a handful of items, then crawls in production when the list holds tens of thousands — because the innocent if item in seen_list is O(n) each call, making the whole loop O(n^2). The fix is always the same one this session drills: swap the list for a set. Engineers who count operations catch this in code review; engineers who go by vibes ship it and get paged. That is the practical value of the habit.

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.