Complexity Analysis and Big-O

Complexity analysis describes how an algorithm's resource requirements grow as its input grows. It helps compare approaches independently of a particular machine, while still requiring careful attention to the operations being counted.

1. Define the input size

Choose variables that describe the input. For an array, let (n) be its length. For a graph, common measures are (V), the number of vertices, and (E), the number of edges. State these definitions before giving a complexity.

2. Common growth rates

Complexity	Name	Typical example
(O(1))	Constant	Array indexing
(O(\log n))	Logarithmic	Binary search on sorted data
(O(n))	Linear	One pass through an array
(O(n\log n))	Linearithmic	Efficient comparison sorting
(O(n^2))	Quadratic	Comparing every pair
(O(2^n))	Exponential	Enumerating all subsets
(O(n!))	Factorial	Enumerating all permutations

These are common patterns, not guarantees about every implementation. For example, hash-table lookup is typically expected (O(1)), but can have worse worst-case behavior.

3. Analyze loops

A single loop over (n) elements is (O(n)).

Two independent nested loops over the same (n) elements are (O(n^2)).

A loop that halves its remaining search space on each iteration is (O(\log n)).

When loops run sequentially, add their costs and keep the dominant term: (O(n) + O(n^2) = O(n^2)).

4. Auxiliary space vs. total space

• Auxiliary space is additional memory used by the algorithm, excluding the input unless stated otherwise.
• Total space includes the input representation and all additional memory.

A recursive algorithm may use stack space proportional to recursion depth. For example, a recursive traversal of a skewed tree can reach (O(n)) call-stack space.

5. Best, average, and worst case

State which case your analysis describes. Binary search has (O(\log n)) worst-case time on a sorted random-access array. Hash-table operations are commonly expected (O(1)), but worst-case lookup can be (O(n)).

6. Example: find a pair with a target sum

Brute force checks every pair, taking (O(n^2)) time and (O(1)) auxiliary space.

A hash-set approach scans once, checking whether the complement has already been seen. It takes expected (O(n)) time and (O(n)) auxiliary space.

def has_pair_with_sum(values: list[int], target: int) -> bool:
    seen: set[int] = set()

    for value in values:
        if target - value in seen:
            return True
        seen.add(value)

    return False

The algorithm checks before inserting the current value, so it does not reuse one array element twice. Duplicate values can still form a valid pair when they occur at different positions.

7. Interview checklist

1. Define input-size variables.
2. Count the dominant operations.
3. Account for nested loops, recursion, and data-structure operations.
4. State average or worst-case assumptions.
5. Separate time, auxiliary space, and total space.
6. Explain whether the complexity is acceptable for the stated constraints.