Big O

Priority: Must. Use the roadmap to decide when to study this topic.

An input size is a variable, not a runtime measurement. Bound time and auxiliary space separately, including recursion and copying; simplify only after deriving the count. Two independent sizes should remain separate variables unless their relationship is known.

Recognition signals

Signals: Repeated scans, growing recursion trees, copying slices, or a required scale.

First question: What exact operation repeats, and how many live objects coexist?

False friend: A nested loop is not automatically quadratic if one pointer never resets.

Retrieval and transfer check

Compare an n-by-n pair scan with two monotone pointers; justify total increments and peak space.

Be careful

Two consecutive loops add their costs; nested independent loops multiply them. A loop that halves its range is logarithmic.

Practice linked to this topic

Intuition

Count how work changes as input grows. Choose a basic operation, count its executions, then simplify the growth rate.

Variations

Worst case

An upper bound over inputs of size n. Linear search may examine every item.

Best and average case

Best case can stop immediately; average case needs an explicit input distribution. Do not infer it from a few timings.

Amortized analysis

Average cost over a sequence, without probabilistic inputs. Dynamic-array append is amortized O(1), although one resize is O(n).

Time and auxiliary space

Count operations and additional storage separately. Recursion frames consume space; output storage should be reported separately.

Multiple input sizes

Use O(n + m) for scanning two independent lists; O(nm) for all cross-list pairs.

Growth families

O(1), O(log n), O(n), O(n log n), O(n²), O(2^n), and O(n!) describe increasingly expensive common shapes. Big O is an upper bound; Theta is a tight bound.

Visual walkthrough

Task: For each input size n, count the visits made by one complete pass and the pair operations made by two nested complete passes. Explain how doubling n changes each count.

Sample input: n = 4, 8, 16

Expected output: One pass: 4, 8, 16 visits. All ordered pairs: 16, 64, 256 pair operations.

Constraints and conventions: n is a positive integer. Count the selected loop-body operation; assume it takes constant time.

1. State: 1 2 3 4. n=4: one pass visits 4 items; all ordered pairs require 16 operations.
2. State: 1 2 3 4 5 6 7 8. n=8: one pass requires 8 visits; all ordered pairs require 64 operations.
3. State: 16 256. Doubling n doubled linear work and quadrupled quadratic work.

Open the static revision frames

Python example

def count_pairs(a):
    return sum(1 for x in a for y in a)
assert count_pairs([1, 2, 3]) == 9

Complexity and pitfalls

O(n²) time, O(1) auxiliary space, counting the nested generator iterations.

Two consecutive loops add their costs; nested independent loops multiply them. A loop that halves its range is logarithmic.

Practice

• Count work in two consecutive loops
• Count triangular nested-loop iterations
• Analyze a loop that repeatedly halves n