Asymptotic Analysis¶

Learning objectives¶

Interpret O, Ω, and Θ as sets of functions.
Analyze sequential, nested, and halving loops.
Distinguish worst-case, average-case, expected, and amortized analysis.

Definitions¶

For eventually non-negative functions f and g:

f(n) ∈ O(g(n)) if constants c > 0 and n₀ exist such that f(n) ≤ c g(n) for every n ≥ n₀.
f(n) ∈ Ω(g(n)) if f is eventually bounded below by a positive constant multiple of g.
f(n) ∈ Θ(g(n)) if both bounds hold.

O(g(n)) is an asymptotic upper bound, not necessarily an exact or tight description. Saying binary search is O(n) is true but uninformative; its worst-case running time is more precisely Θ(log n).

Growth rates¶

Class	Typical example
`Θ(1)`	Array access by valid index
`Θ(log n)`	Binary search
`Θ(n)`	Scanning an array
`Θ(n log n)`	Merge sort
`Θ(n²)`	Comparing every pair
`Θ(2ⁿ)`	Enumerating all subsets
`Θ(n!)`	Enumerating all permutations

Logarithm bases differ only by a constant factor, so asymptotic notation usually omits the base.

Counting operations¶

for i = 0 to n - 1
    for j = i + 1 to n - 1
        visit(i, j)

The number of visits is (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2, which is Θ(n²).

A loop that repeatedly divides the remaining problem by two runs ⌊log₂ n⌋ + O(1) iterations, which is Θ(log n).

Cases and probability¶

Worst case: maximum cost among inputs of size n.
Best case: minimum cost among inputs of size n.
Average case: expected cost under an explicitly stated input distribution.
Expected cost: expectation over input randomness, algorithm randomness, or both; the probability space must be stated.
Amortized cost: average per operation over every valid operation sequence; it requires no probability distribution.

Dynamic-array append is a classic amortized O(1) operation even though an individual resizing append costs Θ(n).

Space¶

This site reports peak auxiliary space. Recursion contributes stack frames. An in-place algorithm normally uses O(1) auxiliary storage, although definitions may permit O(log n) call-stack space; each page states its convention.

Exercises¶

Analyze a loop whose index doubles after each iteration.
Show that 3n² + 7n + 4 ∈ Θ(n²) from the definition.
Explain why average-case and amortized analysis are different.