Analysing Real Code

Knowing the theory is one thing. Quickly deriving the complexity of actual code is another. This lesson builds that muscle with worked examples and common traps.

The Step-by-Step Method

When analysing a function:

1. Identify the input size variable(s) — usually n, sometimes m and n for two inputs.
2. Count operations inside loops and recursive calls in terms of n.
3. Add complexities for sequential sections; multiply for nested sections.
4. Drop constants and lower-order terms.
5. Keep the dominant term.

Example 1: Sequential Loops

def process(arr):
    total = 0
    for x in arr:        # O(n)
        total += x

    result = []
    for x in arr:        # O(n)
        if x > 0:
            result.append(x)

    return total, result

Two O(n) loops in sequence: O(n) + O(n) = O(2n) → O(n).

Example 2: Nested Loops — Different Variables

def print_pairs(arr, queries):
    for q in queries:         # O(m) — m = len(queries)
        for x in arr:         # O(n) — n = len(arr)
            print(q, x)

The outer loop runs m times, inner loop runs n times: O(m × n). If m and n are the same size, this is O(n²). If m is small and constant (say, always 3 queries), it is O(n). The variable names matter.

Example 3: Loop with Early Exit

def linear_search(arr, target):
    for i, x in enumerate(arr):    # at most n iterations
        if x == target:
            return i
    return -1

Best case: O(1) (target is first). Average case: O(n/2) → O(n). Worst case: O(n) (target not found or last element). Big O is the worst case: O(n).

Example 4: Recursion — Identifying Depth and Branching

Use the recurrence relation approach:

def sum_recursive(arr, i=0):
    if i == len(arr):
        return 0
    return arr[i] + sum_recursive(arr, i + 1)

• Each call does O(1) work.
• Recursion depth: n levels.
• O(n) time, O(n) stack space.

def power(base, exp):
    if exp == 0:
        return 1
    half = power(base, exp // 2)   # one recursive call
    if exp % 2 == 0:
        return half * half
    return base * half * half

• Each call halves exp.
• Depth: log₂(exp) levels.
• O(log n) time (where n = exp).

Example 5: Hidden O(n) Inside a Loop

Built-in operations can hide complexity:

def bad_contains_check(arr):
    result = []
    for x in arr:               # O(n)
        if x not in result:     # O(k) where k = len(result)
            result.append(x)
    return result

x not in result is O(k) for a list — it scans the list linearly. As result grows, this becomes progressively slower. Total: O(1 + 2 + 3 + ... + n) = O(n²).

Fix: use a set.

def good_contains_check(arr):
    seen = set()
    result = []
    for x in arr:         # O(n)
        if x not in seen: # O(1) average for a set
            seen.add(x)
            result.append(x)
    return result

Now O(n). The code looks similar; the complexity is entirely different.

Example 6: String Concatenation Trap

def join_naive(words):
    result = ""
    for word in words:       # n words
        result += word       # creates a new string each time
    return result

String concatenation in many languages (Python, Java) creates a new string object each iteration. If average word length is k, the total work is k + 2k + 3k + ... + nk = O(n²k). For short words, this looks like O(n²).

Fix:

def join_efficient(words):
    return "".join(words)    # O(n) — one pass, one allocation

Example 7: Sorting Changes Everything

def has_duplicate(arr):
    arr.sort()                      # O(n log n)
    for i in range(len(arr) - 1):  # O(n)
        if arr[i] == arr[i + 1]:
            return True
    return False

Sorting dominates: O(n log n). The linear scan after is a lower-order term.

Compare to the hash set approach:

def has_duplicate_hash(arr):
    return len(arr) != len(set(arr))   # O(n) time, O(n) space

O(n) time, O(n) space vs O(n log n) time, O(1) extra space — classic tradeoff.

Common Complexity Signatures at a Glance

Key Takeaways

• Sequential code sections add their complexities; nested sections multiply.
• Always identify what n refers to — different inputs have different sizes.
• Built-in operations have complexity too: list in, string concatenation, and list insert are common O(n) traps.
• Sort dominates linear operations — an O(n log n) sort followed by an O(n) pass is O(n log n) overall.
• When you see recursion, identify the depth and branching factor to derive the complexity.