Algo Complexity Analysis

Algorithmic Complexity Analysis (Big O)

When to Use

• Asked to state or derive the time/space complexity ("what's the Big O of this function") of a code snippet or algorithm
• Reviewing code for hidden quadratic behavior: in on a list inside a loop, += string concatenation, sorted() inside a loop
• Choosing between data structures/algorithms for scale (list vs set membership, sort vs heap)
• Deriving recursive complexity via a recurrence relation, e.g. T(n) = 2T(n/2) + n (Master theorem)
• Explaining best/average/worst-case or amortized cost (list.append, hash table lookup, quicksort pivot choice)

Version Compatibility

• Language-agnostic technique; example code uses Python ≥3.8 stdlib only (math, no third-party dependencies)

Prerequisites

• Comfortable reading Python loops, function calls, and recursion
• No packages to install

Complexity Classes (fastest to slowest)

Simplification Rules

O(2n + 5)    →  O(n)      # drop constants
O(n² + n)    →  O(n²)     # drop lower-order terms
O(500)       →  O(1)
O(n² + n³)   →  O(n³)
O(A) then O(B)  →  O(A + B)   # sequential loops add
O(A) inside O(B) →  O(A × B)  # nested loops multiply

Goal: classify the complexity of straight-line and loop-based code. Approach: identify the loop structure (single / nested / sequential / halving), express operation count as a function of n, then apply the simplification rules above.

def get_first_element(arr):
    """Return the first element. O(1) time, O(1) space.

    Direct index access: base_address + index * element_size,
    independent of array length.
    """
    return arr[0] if arr else None


def binary_search(arr, target):
    """Find target in a sorted array. O(log n) time, O(1) space.

    Each iteration halves the search space: after k steps the
    remaining size is n / 2**k, so it terminates in ~log2(n) steps.
    """
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2       # O(1)
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1               # discard left half
        else:
            right = mid - 1              # discard right half
    return -1


def has_duplicate_naive(arr):
    """O(n²) time, O(1) space: compares every pair of elements."""
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] == arr[j]:
                return True
    return False


def has_duplicate_fast(arr):
    """O(n) time, O(n) space: trades memory for speed via a set."""
    seen = set()
    for x in arr:
        if x in seen:        # O(1) average membership test
            return True
        seen.add(x)
    return False

Goal: derive complexity of recursive functions. Approach: write the recurrence relation T(n) = a*T(n/b) + f(n) (Master theorem form), then match it to a known pattern.

def merge_sort(arr):
    """Sort via divide-and-conquer. O(n log n) time, O(n) space.

    Recurrence: T(n) = 2*T(n/2) + O(n)  ->  O(n log n)
    (log n levels of recursion, O(n) merge work per level)
    """
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return _merge(left, right)


def _merge(left, right):
    """Merge two sorted lists. O(n) time, O(n) space."""
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result


def fibonacci_naive(n):
    """Naive recursive Fibonacci. O(2^n) time, O(n) space (call stack).

    Recurrence: T(n) = T(n-1) + T(n-2) + O(1)  ->  O(2^n)
    Each call branches into two more calls, forming a binary call tree.
    """
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

At Scale (n = 1,000,000)

Best / Average / Worst

Amortized Complexity

• Python list.append(): O(1) amortized (occasional O(n) resize when capacity doubles, but rare)
• Python dict/set lookup: O(1) average; O(n) worst case (pathological hash collisions — rare with good hashing)

Pitfalls

• Hidden O(n) inside a loop: x in some_list is O(n); inside an O(n) loop that's O(n²). Use a set for O(1) membership (see has_duplicate_fast above).
• String concatenation: s += x in a loop reallocates and copies each time → O(n²) total. Use ''.join(parts).
• sorted() is O(n log n): calling it inside a loop makes the loop O(n² log n) — sort once outside the loop.
• Recursion depth: unbounded recursion on large n hits Python's default ~1000-frame limit. Prefer an iterative rewrite over raising sys.setrecursionlimit.
• Space vs time trade-off: memoization/hash sets trade O(n) space for O(n²) → O(n) or O(1) repeated lookups.
• Worst-case vs average-case: quicksort degrades to O(n²) on already-sorted input with a naive pivot; use random/median-of-three pivot selection or Python's built-in Timsort (sorted()/list.sort()), which is O(n log n) worst case.

See Also

• algo-basic-algorithms — foundational search/sort algorithms referenced above
• algo-linear-binary-search — linear vs binary search trade-offs in depth
• algo-comparison-sorts — merge sort, quicksort, heapsort implementations
• algo-intro-memoization — turning exponential recursion into polynomial time