Analyzing Your Own Solutions

Writing a working solution is only half the job. The other half is being able to look at code you just wrote — your own or someone else’s — and say precisely how it will behave as the input grows: how many operations it does, how much memory it uses, and where the slow part is hiding. This skill matters more than memorizing any single algorithm, because in an interview or a code review you will constantly be asked "what’s the complexity of this?" about code nobody has seen before, including your own first draft.

This lesson is not about one data structure or algorithm. It is about the process of reading code and deriving its Big-O — a skill you apply to every other lesson in this course.

Overview: How to Analyze a Solution

Analyzing a solution is a repeatable process. Follow these steps every time:

1. Name the input size variable(s). Call the length of your main input n (and m, V/E, etc. if there’s a second input or a graph). Every complexity you state must be described in terms of these variables — "it’s fast" is not an answer; "O(n)" is.

2. Find every loop and every recursive call. These are where repeated work happens. A single for loop over the input is a strong signal of at least O(n) work. A recursive function that calls itself is doing repeated work just like a loop, and needs the same kind of accounting.

3. Determine the cost of one iteration or one call. Is the body of the loop O(1) (a comparison, an arithmetic op, a dict lookup), or does it itself scan a structure (making it O(n) per iteration)? This is the step people skip, and it’s the most common source of a wrong answer.

4. Combine according to nesting, not just counting. Two loops back-to-back (not nested) add: O(n) + O(n) = O(n). Two loops nested inside each other multiply: O(n) * O(n) = O(n2). For recursion, the accounting is different again — you multiply the number of calls by the work per call, or use a recurrence relation.

5. Separate time from space. Time complexity counts operations executed; space complexity counts extra memory allocated (not counting the input itself, unless you copy it). A recursive function that never allocates an explicit data structure can still use O(n) space, because every unfinished call sits on the call stack.

6. Ask whether best, average, and worst case differ. A hash-map lookup is O(1) on average but O(n) in the rare worst case of many collisions. A linear search is O(n) in the worst case but O(1) if the target happens to be first. State the case you mean.

Let’s ground this in a concrete scenario before looking at more examples: the classic "two sum" problem — given a list of numbers, find two whose sum equals a target. A brute-force approach checks every pair; a hash-map approach remembers what it has seen. Analyzing both is the fastest way to see the process above in action, and it’s the first worked example below.

Time and Space Complexity

Most solutions you write are built out of a small number of recurring shapes. Learn to recognize the shape, and the complexity follows automatically.

Code shape Time Why
Single loop over n elements, O(1) work per step O(n) The loop body runs n times, each step costs a constant amount of work.
Two independent loops, one after another O(n) Sequential work adds: O(n) + O(n) simplifies to O(n) once constants are dropped.
Nested loop, inner loop runs n times for each of n outer steps O(n2) The inner loop’s n steps happen once for every one of the outer loop’s n steps: n * n.
Loop that cuts the remaining range in half each step (e.g. binary search) O(log n) The range shrinks geometrically, so it takes about log₂(n) steps to reach size 1.
Linear recursion (one recursive call per invocation, e.g. summing a list recursively) O(n) time, O(n) space n calls are made, each doing O(1) work; each unfinished call stays on the call stack, so the stack grows to depth n.
Branching recursion with no memoization (e.g. naive Fibonacci) O(2n) time, O(n) space Each call spawns two more calls, so the call tree roughly doubles in size at each level; but only one root-to-leaf path is on the stack at once, so space stays linear in the recursion depth.
Same recursion with memoization (caching results) O(n) time, O(n) space Each distinct subproblem (there are only n of them) is computed once and then reused from the cache; the cache itself costs O(n) space.
Membership check (in) on a set or dict O(1) average, O(n) worst case Hashing places elements so lookup is direct in the typical case; heavy hash collisions degrade this to a linear scan.
Membership check (in) on a list O(n) Python must scan the list element by element until it finds a match or reaches the end.
String concatenation with += inside a loop, n times O(n2) Strings are immutable, so each += builds an entirely new string; the total characters copied across all iterations sum to 1 + 2 + … + n.

Examples

Each example below shows two solutions to the same problem so you can practice comparing their complexity directly.

Example 1: Two Sum — brute force vs. hash map

def two_sum_brute_force(nums: list[int], target: int) -> list[int]:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []


def two_sum_hashmap(nums: list[int], target: int) -> list[int]:
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []


nums = [2, 7, 11, 15]
target = 9
print(two_sum_brute_force(nums, target))
print(two_sum_hashmap(nums, target))

Output:

[0, 1]
[0, 1]

Both return the same answer, but analyzing them shows very different costs. two_sum_brute_force has a loop nested inside a loop, both ranging over roughly n elements, so it does O(n2) comparisons in the worst case, and uses O(1) extra space. two_sum_hashmap makes a single pass, and the expensive-looking line — checking complement in seen — is an O(1) average dict lookup, not a scan. So the whole function is O(n) time, at the cost of O(n) extra space for the seen dictionary. This is the single most common tradeoff you will make: spend O(n) space to buy back an order of magnitude in time.

Example 2: Naive vs. memoized recursion

def fib_naive(n: int) -> int:
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


def fib_memo(n: int, cache: dict[int, int] | None = None) -> int:
    if cache is None:
        cache = {}
    if n <= 1:
        return n
    if n in cache:
        return cache[n]
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]


print(fib_naive(10))
print(fib_memo(10))

Output:

55
55

Both functions compute the 10th Fibonacci number and agree on the answer, 55. But look at the recursive calls. fib_naive recomputes the same subproblems over and over — fib_naive(5) gets called many times as part of computing fib_naive(10) — so the number of calls roughly doubles with every increase in n, giving O(2n) time. fib_memo stores each result in cache the first time it's computed, so every value from 0 to n is computed exactly once: O(n) time, plus O(n) space for the cache and the recursion stack. Notice also that fib_memo uses cache: dict[int, int] | None = None rather than a mutable default argument — see Common Mistakes below for why that matters.

Example 3: A hidden O(n2) in plain-looking code

def build_string_slow(words: list[str]) -> str:
    result = ""
    for word in words:
        result += word + " "
    return result.strip()


def build_string_fast(words: list[str]) -> str:
    return " ".join(words)


words = ["analyze", "your", "own", "solutions"]
print(build_string_slow(words))
print(build_string_fast(words))

Output:

analyze your own solutions
analyze your own solutions

Both print the same sentence, but build_string_slow is a classic case of complexity hiding in code that looks like a single, innocent loop. Because Python strings are immutable, every result += word + " " creates a brand-new string and copies all the previously accumulated characters into it. Summed over n words, that is 1 + 2 + ... + n character copies, which is O(n2). build_string_fast uses str.join, which knows the total length up front and builds the result once: O(n). The lesson: a single for loop is not automatically O(n) — you must check what each iteration actually costs.

How It Works Step by Step

Let's apply the full analysis process to one more function, line by line, the way you should talk through your own code in an interview:

def has_duplicate(nums: list[int]) -> bool:
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False


nums = [4, 2, 7, 2, 9]
print(has_duplicate(nums))

Output:

True

Trace it exactly as the interpreter would, on nums = [4, 2, 7, 2, 9]:

  • seen = set() — O(1) time, starts at O(1) space.
  • num = 4: is 4 in seen? seen is empty, so no. Add it: seen = {4}.
  • num = 2: is 2 in seen? No. Add it: seen = {4, 2}.
  • num = 7: is 7 in seen? No. Add it: seen = {4, 2, 7}.
  • num = 2: is 2 in seen? Yes — 2 is already there. Return True immediately.

Now the complexity: the loop runs at most n times (it can exit early, which only helps the best case). Each iteration does one set membership check and possibly one set insertion, both O(1) on average because Python's set is hash-based. So total time is O(n) on average. Space is O(n) in the worst case (an input with no duplicates forces every element into seen). This is exactly the pattern from Example 1's hash-map solution: trade O(n) space for O(1)-average lookups instead of O(n) list scans.

Common Mistakes

Mistake 1: Assuming a list membership check is O(1)

It's easy to write a duplicate-check using a list as the "seen" tracker and not notice that you've built a hidden nested loop:

def has_duplicate_slow(nums: list[int]) -> bool:
    seen = []
    for num in nums:
        if num in seen:
            return True
        seen.append(num)
    return False


nums = [4, 2, 7, 2, 9]
print(has_duplicate_slow(nums))

Output:

True

The output matches the set-based version, so it looks equivalent — but it is not equivalent in cost. num in seen on a list scans every element already stored, so in the worst case (no duplicates until the very end, or none at all) this is O(n) work happening inside a loop that runs O(n) times, giving O(n2) overall. The fix is exactly the has_duplicate function shown above: swap the list for a set, which turns the inner check into O(1) on average and the whole function into O(n).

Mistake 2: The mutable default argument trap, hiding as a "complexity-free" helper

When analyzing your own solutions, don't just check Big-O — check that repeated calls behave independently. This bug is notorious because the code runs without error and silently gives the wrong answer:

def add_to_list(item, target=[]):
    target.append(item)
    return target


print(add_to_list(1))
print(add_to_list(2))

Output:

[1]
[1, 2]

The second call prints [1, 2] instead of the probably-intended [2]. The default value [] is created exactly once, when the function is defined, and every call that omits target reuses that same list object — so state leaks between calls that look independent. This is especially dangerous in recursive or backtracking helpers that accumulate results, because it can look like a complexity bug ("why does this grow larger than I expect?") when it's actually a correctness bug. Fix it by defaulting to None and creating a fresh list inside the function:

def add_to_list(item, target: list | None = None) -> list:
    if target is None:
        target = []
    target.append(item)
    return target


print(add_to_list(1))
print(add_to_list(2))

Output:

[1]
[2]

Best Practices

  • Identify the input-size variable first (n, m, V/E) before trying to state a complexity — a Big-O without a variable is meaningless.
  • Read every line inside a loop and ask "what does this operation cost?" before assuming a single loop means O(n) — a list in check, a slice, or a string concatenation inside the loop can silently make it O(n2).
  • For recursive code, count both the number of calls and the work per call, and separately track the maximum call-stack depth for space — don't assume recursion is automatically O(n).
  • State best, average, and worst case explicitly when they differ (hash maps, quicksort) rather than giving one number that only applies sometimes.
  • When you find an O(n2) pattern caused by repeated linear scans, check whether a set or dict can convert those scans into O(1) average lookups at the cost of O(n) space — this trade shows up constantly.
  • Test your complexity intuition against a mental trace of a small input (5-10 elements), the same way you'd trace correctness, rather than only reasoning abstractly.
  • When accumulating results in recursive or repeated calls, always default mutable arguments to None and build the container inside the function.

Practice Exercises

  • Exercise 1: You have a function that checks whether two lists share any common element by looping over the first list and, for each element, looping over the second list to check for a match. State its time complexity in terms of the two list lengths, then rewrite it to run in linear time using a set. Hint: what data structure gives O(1) average membership checks?
  • Exercise 2: Write a recursive function that computes the nth triangular number (1 + 2 + ... + n) by calling itself with n - 1. State its time and space complexity, and identify the base case that prevents infinite recursion.
  • Exercise 3: Take any loop you've written recently that builds up a string with += inside the loop. Rewrite it to collect pieces in a list and join them at the end, then state the time complexity before and after the change.

Summary

  • Analyzing a solution means naming the input size variable, locating every loop and recursive call, determining the cost per iteration or call, and combining those costs according to whether the structures are sequential (add) or nested (multiply).
  • Time complexity counts operations relative to input size; space complexity counts extra memory beyond the input, including the recursion call stack.
  • Common shapes: a single O(1)-per-step loop is O(n); nested loops multiply to O(n2); halving loops are O(log n); naive branching recursion is O(2n) while memoized recursion drops to O(n).
  • set/dict membership checks are O(1) on average versus O(n) for a list — this is the most common way to turn an O(n2) solution into O(n).
  • String concatenation with += in a loop is a hidden O(n2); build with a list and str.join for O(n).
  • Always state best/average/worst case when they differ, and double-check recursive helpers for mutable default argument bugs, which are correctness issues that masquerade as unexplained growth.