1.2 Common Complexity Analysis

After reading What Is Complexity?, spend about 30 minutes analyzing loops, branches, multiple inputs, and additional space usage. The goal isn't to guess complexity from indentation, instead, first write out an expression for the number of operations, then state the time complexity with appropriate assumptions.

From "Looks Like" to "Calculates"

1. What is the input, and what do the size variables represent?
2. Which fundamental operation are we counting?
3. How many times is each code block executed?
4. When adding sequential blocks, summing nested ranges, or multiplying, what is the resulting expression?
5. Are we analyzing best-case, worst-case, average-case, expected, or amortized cost?
6. How much input, output, and auxiliary space is used?

By following these six steps, complexity is no longer a guessed label, it becomes a verifiable derivation.

Sequential Execution: Add First

def summarize(left, right):
    left_total = 0
    for value in left:
        left_total += value

    right_total = 0
    for value in right:
        right_total += value

    return left_total, right_total

Let n = len(left) and m = len(right). The two loops execute one after the other, with operation counts approximately equal to n + m, so the time complexity is Θ(n + m), not Θ(nm).

If m = O(n), for example m equals n, is constant, or is bounded by n, the expression simplifies to Θ(n). Without such a constraint, keep both variables. Keeping the independent variables allows callers to see the true direction of expansion.

The two sequential loops over the same input can be combined to extract the dominant term:

3n + 2n + 10 = 5n + 10 = Θ(n)

The final equality here refers to classification of growth rate, not to claiming that the actual work reduces to just n steps.

Nested Execution: First Look at Scope

Two Complete, Independent Ranges

def matches(left, right):
    result = []
    for first in left:
        for second in right:
            if first == second:
                result.append((first, second))
    return result

The outer n loop runs fully, executing the complete m-iteration inner loop each time. This results in nm comparisons and takes Θ(nm) time. Creating and appending k result tuples adds Θ(k) work and output space; returning the list reference itself does not copy them. Here k ≤ nm. The Θ(nm) shorthand assumes both ranges are nonempty; when m is 0, the outer loop still runs n times.

A Range Dependent on Outer Loop Position

def unordered_pairs(values):
    result = []
    for left in range(len(values)):
        for right in range(left + 1, len(values)):
            result.append((values[left], values[right]))
    return result

The inner loop does not execute n times on every iteration. The exact number of iterations is:

(n - 1) + (n - 2) + ... + 1 + 0
= n(n - 1) / 2
= Θ(n²)

The asymptotic growth remains quadratic, but the reasoning isn't simply "two nested loops." This version produces n(n - 1)/2 results, so the output space is also Θ(n²).

Nested Execution Does Not Always Multiply to a Square

def shrinking_work(n):
    steps = 0
    remaining = n
    while remaining > 1:
        for _ in range(10):
            steps += 1
        remaining //= 2
    return steps

The cost of ten fixed operations is constant; each iteration halves the problem size. The total number of steps is approximately 10 log₂ n, so the complexity is Θ(log n).

Halve Each Time: Why It's Logarithmic

Binary search halves the search space with each iteration. After k rounds, the remaining size is approximately n / 2^k. When it reaches 1:

n / 2^k ≤ 1
2^k ≥ n
k ≥ log₂ n

This gives Θ(log n) probes in the worst case. A match at the first midpoint takes Θ(1) probes in the best case. Binary search relies on the data being sorted according to the comparison rule being used; if sorting is performed just to enable a single lookup, that sorting cost must also be accounted for in the overall task.

Branches: First Specify Which Scenario to Analyze

def contains(values, target):
    for value in values:
        if value == target:
            return True
    return False

Scenario	Input Characteristics	Comparison Count	Tight Bound
Best-case	First element matches	1	Θ(1)
Worst-case	Last element matches or not found	n	Θ(n)
Average-case	Depends on target position and missing probability	Varies by distribution	Cannot be assumed without justification

The conditional statement itself does not automatically reduce complexity to an average. The worst-case cost is the maximum across reachable branches; average or expected cost must explicitly state where the probabilities originate.

Four Patterns in a Runnable Experiment

The following program requires Python 3.9+. It counts model operations and checks results with assertions. The binary-search counter counts midpoint probes; each probe may perform both an equality comparison and an ordering comparison. Under the usual hashing assumptions, frequency-table construction takes expected linear time, but the hash table conclusions depend on runtime hash and resizing behavior; here we verify the returned content and access count model, not the promise of fixed execution time for all inputs.

# analysis_demo.py

def linear_steps(n: int) -> int:
    steps = 0
    for _ in range(n):
        steps += 1
    return steps

def binary_search_probes(values: list[int], target: int) -> int:
    left = 0
    right = len(values) - 1
    probes = 0

    while left <= right:
        middle = (left + right) // 2
        probes += 1
        if values[middle] == target:
            return probes
        if values[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return probes

def triangular_steps(n: int) -> int:
    steps = 0
    for left in range(n):
        for _ in range(left + 1, n):
            steps += 1
    return steps

def frequency_table(values: list[int]) -> dict[int, int]:
    frequencies: dict[int, int] = {}
    for value in values:
        frequencies[value] = frequencies.get(value, 0) + 1
    return frequencies

def main() -> None:
    linear = linear_steps(8)
    binary = binary_search_probes(list(range(8)), 8)
    triangular = triangular_steps(8)
    frequencies = frequency_table([3, 1, 3, 2, 1, 4, 5, 5])

    assert linear == 8
    assert binary == 4
    assert triangular == 28
    assert frequencies == {3: 2, 1: 2, 2: 1, 4: 1, 5: 2}

    print(f"Linear steps: {linear}")
    print(f"Binary probes: {binary}")
    print(f"Triangular loop steps: {triangular}")
    print(f"Frequency table key count: {len(frequencies)}")
    print("Analysis check passed")

if __name__ == "__main__":
    main()

Run:

python3 analysis_demo.py

Output:

Linear steps: 8
Binary probes: 4
Triangular loop steps: 28
Frequency table key count: 5
Analysis check passed

Item-by-item verification:

• The linear loop fully traverses 8 positions.
• In [0, 1, ..., 7], it searches for a non-existent and larger 8, probing midpoint values 3, 5, 6, 7 in four iterations; this particular search executes eight equality or ordering comparisons.
• There are 8 × 7 / 2 = 28 unordered element pairs.
• Eight input values form five distinct keys; the dictionary itself occupies Θ(u) space, where u is the count of distinct values, and u ≤ n.

Space Complexity: First, Clarify What Kind of Space You're Measuring

Name	What It Includes	Example
Input space	Data passed to the algorithm by the caller	The input values
Output space	Results that must be returned or written out	The list result of unordered_pairs
Auxiliary space	Extra space allocated during algorithm execution	Frequency table, temporary arrays, recursion stack

In engineering and interview settings, when people say "space complexity," they often mean auxiliary space, though this isn't a universal convention. The safest approach is to explicitly state:

Input space Θ(n), Output space Θ(k), Auxiliary space Θ(u)

In-place updates don't mean zero space usage

def double_in_place(values):
    for index in range(len(values)):
        values[index] *= 2

Under unit-cost numeric operations and excluding the input container, this function uses Θ(1) auxiliary space. Longer Python integers require larger results and temporary objects, so their bit lengths must be included in a bit-cost analysis. Loop variables and a few scalar values still consume memory, even though their usage doesn't grow with n.

Recursive stack must be accounted for

def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n < 2:
        return 1
    return n * factorial(n - 1)

Here n is a non-negative integer: 0! and 1! return 1, and negative values are rejected. Treating each multiplication as one step gives Θ(n) calls and stack depth. Actual Python integer multiplication grows with operand size, and n! itself needs Θ(n log n) bits. Large n can also hit Python’s recursion limit. The absence of an explicitly created list does not imply constant space usage.

Average, Expected, and Amortized Are Not the Same Thing

Concept	Requires Probability?	Answers the Question
Average Case	Requires input distribution	If inputs follow a certain distribution, what's the average cost?
Expected Cost	Requires algorithmic randomness and/or input distribution	Under random selection or other stochastic factors, what's the expected cost?
Amortized Cost	Does not require	What is the total cost of a sequence of operations, spread evenly across each operation?

Dynamic array append is a classic example of amortized analysis. Most appends simply write to a single position, but occasionally (when capacity is exceeded) a larger array must be allocated and existing elements copied. In the worst case, a single operation can cost Θ(n). Starting from empty and growing capacity geometrically, the total number of element copies over n consecutive appends remains Θ(n), so the amortized cost per append is Θ(1). This does not mean every individual operation takes constant time, nor does it imply averaging over random inputs.

Common Library Operations Should Be Conditioned

Hash Tables

Hash table lookups are commonly written as expected O(1), typically relying on the following conditions:

• The hash function distributes common keys uniformly;
• The load factor is controlled with a reasonable resizing strategy;
• The cost of hashing and equality comparison for keys is considered constant;
• The input is not specially crafted adversarial data designed to generate many collisions.

The worst-case guarantee depends on the specific implementation, and it's incorrect to state that "hash tables are always O(1)" as a general rule.

Sorting

• Merge sort has a time complexity of Θ(n log n) and typically requires Θ(n) auxiliary space.
• Quick sort achieves average or expected time of Θ(n log n) under reasonable pivot assumptions; however, in cases of persistently unbalanced partitions, the worst-case time becomes Θ(n²).
• Built-in sorting functions in programming languages may use hybrid algorithms. When analyzing real code, you should consult the official specification for the corresponding version, rather than guess the implementation based on the function name alone.

Copying and Slicing

Slicing a built-in Python list creates a new shallow-copy list. Copying a slice of length k requires Θ(k) time and space. Value-based passing in C++ containers, certain copy APIs in Java, string concatenation, and large integer arithmetic can also introduce hidden costs into loop bodies. When analyzing performance, you must expand the actual API calls being made.

Hands-on: Most Frequent Element

def most_common(values):
    if not values:
        return None

    counts = {}
    for value in values:
        counts[value] = counts.get(value, 0) + 1

    winner = None
    winner_count = 0
    for value, count in counts.items():
        if count > winner_count:
            winner = value
            winner_count = count

    return winner

The input here is a list of integers. Ties return the earliest value: since Python 3.7, dictionaries preserve insertion order, and updating a key keeps its position. An empty list returns None; [3, 1, 3, 1] returns 3.

Let n be the input length, and u be the number of distinct values:

1. The first loop runs n times. Under the usual hash assumption, the expected time is Θ(n).
2. The second loop runs u times, with time complexity Θ(u).
3. Because u ≤ n, the total expected time simplifies to Θ(n).
4. The counting table has u keys, and auxiliary space is Θ(u).
5. If the hash or equality comparison of keys is not constant time, or if severe collisions occur, the corresponding costs must be accounted for in the model.

"The two loops thus take 2n, and the final result is O(n)" only performs surface-level arithmetic; the conclusion is only verifiable by someone who writes out u and the hash assumptions explicitly.

Quick Reference

Code Pattern	Expression Written First	Common Tight Bound	Checkpoint
Fixed-Count Operation	c	Θ(1)	Is the operation truly constant-time?
Full Loop	cn	Θ(n)	Could it return early?
Two Sequential Inputs	n + m	Θ(n + m)	Do not arbitrarily assume m = n
Two Nested Full Inputs	nm	Θ(nm)	Must we still produce k outputs?
Triangular Range	n(n-1)/2	Θ(n²)	Does the inner boundary depend on which variable?
Halving Per Iteration	log₂ n	Θ(log n)	Has preprocessing sorting already been completed?
Divide-and-Conquer Sort	2T(n/2) + Θ(n)	Θ(n log n)	Are the subproblems of equal size?
Recursive Chain	T(n-1) + Θ(1)	Θ(n)	Are we tracking the recursive stack depth simultaneously?

Passing Exercise

Don't run it yet, write out the derivation first, then validate the operation count with different scales:

1. Change unordered_pairs to count operations only, without storing results. Does the runtime change? How do the output and auxiliary space change?
2. Analyze "performing binary search on a sorted array of length m for n queries." Which two variables should the answer retain?
3. Find a slicing or copying API you're familiar with in your language, determine whether it returns a view or a copy, and revise the complexity of the loop in question accordingly.
4. Explain why appending to a dynamic array with "amortized Θ(1)" does not equate to "worst-case Θ(1) per operation."

Align the Derivation with the Observed Cost

Reanalyze unordered_pairs: if we only count without persisting the result, the time remains Θ(n²), but the output space drops from Θ(n²). Reexamine "performing binary search on each of n queries in an ordered array of length m", keeping both variables to derive a worst-case bound of Θ(n log(m + 1)). The +1 covers constant query overhead when m is 0 or 1. This worst-case tight bound does not describe inputs where every query matches its first midpoint.

Then locate a real slice, copy, or sort operation and verify whether it's a view or a copy, and determine its preconditions. The amortized Θ(1) of dynamic array appends cannot be rewritten as a worst-case Θ(1) per operation. Professional analysis doesn't chase pretty labels, it only ensures that variables, assumptions, and costs all align.

Reviewing Implementation Contracts

• Python Wiki: Time Complexity: Verify the implementation assumptions behind common container operations.
• Python list.sort: Analyze built-in sorting by first examining its public contract.
• Open Data Structures: Explore loop-based and amortized analyses and the cost implications of various data structures.

Next Step: Formal Bounds and Recurrence Relations

The variables, assumptions, and observed costs now agree. The next step connects O, Ω, Θ, recursion trees, the Master Theorem, and amortized analysis before moving to arrays and linked lists.

Continue learning about asymptotic bounds, recurrence relations, and amortized analysis