Asymptotic notation

Algorithms · Complexity analysis

Asymptotic notation

Asymptotic notation describes how an algorithm’s cost grows as its input becomes large. It ignores machine details and constants, but not the structure of the problem.

What we are measuring

Choose an input-size measure n and count a dominant operation: comparisons, accesses, additions or allocations. Time T(n) and space S(n) are functions of n, not exact seconds or megabytes.

Input

n may count elements, vertices, bits or digits. State it explicitly.

Time

Count how often a meaningful operation is executed.

Auxiliary space

Memory beyond the input itself, including the recursion stack.

Model, not stopwatch. Two algorithms with the same Θ may perform differently in practice; asymptotic analysis explains scaling, not the winner on every input.

The five notations

Symbol	Meaning	Definition	Reading
O(g(n))	Asymptotic upper bound	0 ≤ f(n) ≤ cg(n)	Grows no faster than g, up to a constant.
Ω(g(n))	Asymptotic lower bound	0 ≤ cg(n) ≤ f(n)	Grows at least as fast as g.
Θ(g(n))	Tight bound	c₁g(n) ≤ f(n) ≤ c₂g(n)	Same growth order.
o(g(n))	Strict upper bound	lim f(n)/g(n) = 0	f grows strictly more slowly.
ω(g(n))	Strict lower bound	lim f(n)/g(n) = ∞	f grows strictly faster.

In the first three definitions there are positive constants and a threshold n₀ beyond which the inequality holds. Θ(g(n)) equals O(g(n)) ∩ Ω(g(n)).

O does not mean “worst case”. O is an upper bound. A best-case time can be in O(n²), even when that statement is not tight.

Growth rates

Θ(1)Θ(log n)Θ(n)Θ(n log n)Θ(n²)Θ(n³)Θ(2ⁿ)Θ(n!)

Order	Name	Typical example	n = 1.000
Θ(1)	constant	array access	1
Θ(log n)	logarithmic	binary search	≈ 10
Θ(n)	linear	scan	1.000
Θ(n log n)	linearithmic	merge sort	≈ 10.000
Θ(n²)	quadratic	nested loops	1.000.000
Θ(2ⁿ)	exponential	subset enumeration	impractical

log n uses base 2. Changing the logarithm base only adds a constant factor, so the Θ class is unchanged.

Practical simplification rules

Drop constant factors: 7n² = Θ(n²).
Keep the dominant term: 3n² + 10n + 50 = Θ(n²).
Sequential blocks: add, then keep the maximum. Θ(n) + Θ(n log n) = Θ(n log n).
Independent nested loops: multiply. n · n = Θ(n²).
Branches: name the case. The most expensive branch describes the worst case, not every execution.
Recursion: write a recurrence. For example, merge sort has T(n)=2T(n/2)+Θ(n).

Best, average, worst and amortized cases

Best

Minimum cost among inputs of size n. Useful for adaptive algorithms.

Average

Expected value under a stated probability model for the inputs.

Worst

Maximum cost for an input of size n; it provides a guarantee.

Amortized

Average cost per operation over a sequence, without assuming random inputs.

Three quick analyses

One loop

for i = 0 … n - 1
    visita A[i]

n constant-cost iterations: Θ(n).

Triangle of comparisons

for i = 0 … n - 1
    for j = i + 1 … n - 1

n(n−1)/2 = Θ(n²).

Repeated halving

while n > 1
    n = n / 2

After k steps n/2ᵏ ≤ 1, therefore k = Θ(log n).

Common mistakes

Saying “this algorithm is O(n)” when a tight Θ(n) bound is known: not false, but less informative.
Adding nested-loop costs instead of multiplying them, or multiplying consecutive loops instead of adding them.
Ignoring parameter domains: counting sort depends on both n and the value range k.
Confusing total and auxiliary space, or forgetting the recursive call stack.

Try it yourself

1 · Simplify

8n³ + 2n² log n + 900

Solution

Θ(n³): il termine cubico domina n² log n.

2 · Count

for (i = 1; i < n; i *= 3)

Solution

Θ(log₃ n) = Θ(log n).

3 · Compare

Is n log n = o(n²)?

Solution

Yes: (n log n)/n² = (log n)/n tends to 0.