Time & Space Complexity (Big-O)

Big-O notation describes how the cost of an algorithm — time it takes, or memory it uses — grows as the input size n grows, ignoring constant factors and lower-order terms. It is not a stopwatch measurement; a function timed at 2 milliseconds on your laptop tells you almost nothing about how it behaves at n = 10,000,000. Big-O answers a different question: "if I double the input, roughly how much more work happens?" That's the question interviewers actually care about, and it's the same question that decides whether your code still runs in production once real traffic shows up.

O(1) — Constant Time

Cost does not depend on n at all — the same number of steps whether the input has 10 elements or 10 million.

def get_first(items):
    return items[0]  # direct index lookup, no scanning

Time complexity: O(1) — a Python list index lookup is a direct memory offset calculation regardless of list length. Space complexity: O(1) — no extra memory is allocated.

O(log n) — Logarithmic Time

Cost grows by roughly one step every time n doubles, because the work discards half the remaining input at each step — the hallmark of binary search.

def binary_search(sorted_items, target):
    lo, hi = 0, len(sorted_items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_items[mid] == target:
            return mid
        elif sorted_items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Time complexity: O(log n) — each iteration halves the search range, so for n items there are at most log₂(n) iterations. Space complexity: O(1) — only a constant number of index variables are used, regardless of n.

O(n) — Linear Time

Cost grows in direct proportion to n — a single pass over the input, doing a constant amount of work per element.

def find_max(items):
    current_max = items[0]
    for item in items[1:]:
        if item > current_max:
            current_max = item
    return current_max

Time complexity: O(n) — every element is visited exactly once. Space complexity: O(1) — only one running variable is kept, independent of list size.

O(n log n) — Linearithmic Time

The signature cost of efficient comparison-based sorting: roughly n passes, each doing O(log n) work (or log n passes, each doing O(n) work) — this is exactly what list.sort() and Python's sorted() deliver under the hood (Timsort).

items = [5, 1, 4, 2, 8]
sorted_items = sorted(items)  # Timsort under the hood

Time complexity: O(n log n) — Timsort's worst-case and average-case bound for comparison sorting. Space complexity: O(n) — Timsort is not in-place; it needs auxiliary space proportional to the input in the worst case.

O(n²) — Quadratic Time

The signature cost of a loop nested inside another loop, each running roughly n times — comparing every element against every other element.

def has_duplicate_pair_brute_force(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Time complexity: O(n²) — for each of the n outer iterations, the inner loop does up to n more comparisons. Space complexity: O(1) — no extra structure beyond the loop counters.

O(2ⁿ) — Exponential Time

Cost doubles with every additional unit of input — typical of naive recursive solutions that explore every subset or every branching choice, such as an unmemoized Fibonacci or brute-force subset generation.

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

Time complexity: O(2ⁿ) — each call spawns two more calls, forming a binary call tree roughly 2ⁿ nodes deep. Space complexity: O(n) — the recursion depth (call stack) only goes as deep as n, even though the total number of calls is exponential.

Best, Worst, and Average Case