Chapter 3: Growth of Functions

The order of growth of the running time of an algorithm gives a simple characterization of the algorithm's efficiency and allows us to compare the relative performance of alternative algorithms. Once the input size n becomes large enough, merge sort with its Θ(n lg n) worst-case running time beats insertion sort, whose worst-case running time is Θ(n²).

When we look at input sizes large enough to make only the order of growth of the running time relevant, we are studying the asymptotic efficiency of algorithms — how the running time increases with the size of the input in the limit, as the size of the input increases without bound.

Usually, an algorithm that is asymptotically more efficient will be the best choice for all but very small inputs.

---

Asymptotic Notation

The notations we use to describe the asymptotic running time of an algorithm are defined in terms of functions whose domains are the set of natural numbers N = {0, 1, 2, ...}. These notations are convenient for describing the worst-case running-time function T(n), which usually is defined only on integer input sizes.

Asymptotic Notation, Functions, and Running Times

• Asymptotic notation is primarily used to describe running times of algorithms
• It actually applies to functions — e.g., writing Θ(n²) refers to the function an² + bn + c
• It can also apply to functions characterizing other aspects of algorithms (e.g., space usage) or functions unrelated to algorithms entirely
• When applied to running time, we need to understand which running time we mean: worst-case, best-case, or a blanket statement covering all inputs

Θ-Notation (Theta)

For a given function g(n), Θ(g(n)) denotes the set of functions:

Θ(g(n)) = { f(n) : there exist positive constants c₁, c₂, and n₀ such that
0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n) for all n ≥ n₀ }

• A function f(n) belongs to Θ(g(n)) if it can be sandwiched between c₁g(n) and c₂g(n) for sufficiently large n
• We write f(n) = Θ(g(n)) to mean f(n) ∈ Θ(g(n)) (abusing equality to mean set membership)
• g(n) is called an asymptotically tight bound for f(n)
• Every member f(n) ∈ Θ(g(n)) must be asymptotically nonnegative (nonnegative for sufficiently large n)
• g(n) itself must be asymptotically nonnegative, or else Θ(g(n)) is empty

Example: Show that ½n² − 3n = Θ(n²).

We need positive constants c₁, c₂, and n₀ such that c₁n² ≤ ½n² − 3n ≤ c₂n². Dividing by n²:

• c₁ ≤ 1/2 − 3/n ≤ c₂
• Right inequality holds for any n ≥ 1 by choosing c₂ ≥ 1/2
• Left inequality holds for any n ≥ 7 by choosing c₁ ≤ 1/14
• Choose c₁ = 1/14, c₂ = 1/2, n₀ = 7 ✓

Counterexample: 6n³ ≠ Θ(n²), because 6n³ ≤ c₂n² implies n ≤ c₂/6, which cannot hold for arbitrarily large n.

Key intuition: Lower-order terms of an asymptotically positive function can be ignored. The coefficient of the highest-order term can also be ignored (it only changes c₁ and c₂ by a constant factor).

• For any polynomial p(n) = Σᵢ₌₀ᵈ aᵢnⁱ where aᵈ > 0: p(n) = Θ(nᵈ)
• Any constant function can be expressed as Θ(1) (i.e., Θ(n⁰))

O-Notation (Big-Oh)

When we have only an asymptotic upper bound, we use O-notation.

O(g(n)) = { f(n) : there exist positive constants c and n₀ such that
0 ≤ f(n) ≤ cg(n) for all n ≥ n₀ }

• Provides an upper bound on a function, to within a constant factor
• f(n) = Θ(g(n)) implies f(n) = O(g(n)), since Θ is a stronger notion: Θ(g(n)) ⊆ O(g(n))
• Any quadratic an² + bn + c (a > 0) is in O(n²)
• Any linear function an + b is also in O(n²) — O-notation does not require tightness
• In this book, f(n) = O(g(n)) merely claims some constant multiple of g(n) is an asymptotic upper bound, with no claim about tightness

Practical use:

• The doubly nested loop structure of insertion sort immediately yields an O(n²) upper bound on worst-case running time
• O-notation on worst-case running time gives a bound on every input (a blanket statement)
• The Θ(n²) worst-case bound does NOT imply Θ(n²) on every input (e.g., already-sorted input runs in Θ(n))

Ω-Notation (Omega)

Ω-notation provides an asymptotic lower bound.

Ω(g(n)) = { f(n) : there exist positive constants c and n₀ such that
0 ≤ cg(n) ≤ f(n) for all n ≥ n₀ }

Theorem 3.1: For any two functions f(n) and g(n):

f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n))

• When we say the running time of an algorithm is Ω(g(n)), we mean: no matter what input of size n is chosen, the running time is at least a constant times g(n) for sufficiently large n
• Equivalently, we are giving a lower bound on the best-case running time
• Example: best-case running time of insertion sort is Ω(n), which implies the running time of insertion sort is Ω(n)
• Insertion sort's running time belongs to both Ω(n) and O(n²)

Asymptotic Notation in Equations and Inequalities

• Right-hand side alone: n = O(n²) means n ∈ O(n²) (set membership)
• Within a formula: 2n² + 3n + 1 = 2n² + Θ(n) means there exists some f(n) ∈ Θ(n) such that 2n² + 3n + 1 = 2n² + f(n)
• Left-hand side: 2n² + Θ(n) = Θ(n²) means: no matter how the anonymous functions are chosen on the left, there is a way to choose the anonymous functions on the right to make the equation valid
• Chaining: 2n² + 3n + 1 = 2n² + Θ(n) = Θ(n²) — each equation is interpreted separately; the chain implies 2n² + 3n + 1 = Θ(n²)

o-Notation (Little-Oh)

o-notation denotes an upper bound that is not asymptotically tight.

o(g(n)) = { f(n) : for any positive constant c > 0, there exists a constant
n₀ > 0 such that 0 ≤ f(n) < cg(n) for all n ≥ n₀ }

• Example: 2n = o(n²), but 2n² ≠ o(n²)
• Key difference from O-notation: In O, the bound holds for some constant c > 0; in o, it holds for all constants c > 0
• Intuitively, f(n) becomes insignificant relative to g(n) as n → ∞:

lim (n→∞) f(n)/g(n) = 0

ω-Notation (Little-Omega)

ω-notation denotes a lower bound that is not asymptotically tight.

f(n) ∈ ω(g(n)) if and only if g(n) ∈ o(f(n))

Formally:

ω(g(n)) = { f(n) : for any positive constant c > 0, there exists a constant
n₀ > 0 such that 0 ≤ cg(n) < f(n) for all n ≥ n₀ }

• Example: n²/2 = ω(n), but n²/2 ≠ ω(n²)
• The relation f(n) = ω(g(n)) implies:

lim (n→∞) f(n)/g(n) = ∞

Comparing Functions

Many relational properties of real numbers apply to asymptotic comparisons (assume f(n) and g(n) are asymptotically positive):

Transitivity:

• f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⟹ f(n) = Θ(h(n))
• f(n) = O(g(n)) and g(n) = O(h(n)) ⟹ f(n) = O(h(n))
• f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⟹ f(n) = Ω(h(n))
• f(n) = o(g(n)) and g(n) = o(h(n)) ⟹ f(n) = o(h(n))
• f(n) = ω(g(n)) and g(n) = ω(h(n)) ⟹ f(n) = ω(h(n))

Reflexivity:

• f(n) = Θ(f(n))
• f(n) = O(f(n))
• f(n) = Ω(f(n))

Symmetry:

• f(n) = Θ(g(n)) ⟺ g(n) = Θ(f(n))

Transpose Symmetry:

• f(n) = O(g(n)) ⟺ g(n) = Ω(f(n))
• f(n) = o(g(n)) ⟺ g(n) = ω(f(n))

Analogy with real numbers:

Trichotomy does NOT hold: Not all functions are asymptotically comparable. For example, n and n^(1+sin n) cannot be compared because the exponent oscillates between 0 and 2.

---

Standard Notations and Common Functions

Monotonicity

• Monotonically increasing: m ≤ n ⟹ f(m) ≤ f(n)
• Monotonically decreasing: m ≤ n ⟹ f(m) ≥ f(n)
• Strictly increasing: m < n ⟹ f(m) < f(n)
• Strictly decreasing: m < n ⟹ f(m) > f(n)

Floors and Ceilings

• ⌊x⌋ (floor): greatest integer ≤ x
• ⌈x⌉ (ceiling): least integer ≥ x
• For all real x: x − 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1
• For any integer n: ⌈n/2⌉ + ⌊n/2⌋ = n

Key identities (for real x ≥ 0, integers a, b > 0):

• ⌈⌈x/a⌉ / b⌉ = ⌈x / (ab)⌉
• ⌊⌊x/a⌋ / b⌋ = ⌊x / (ab)⌋
• ⌈a/b⌉ ≤ (a + (b−1)) / b
• ⌊a/b⌋ ≥ (a − (b−1)) / b

Both floor and ceiling functions are monotonically increasing.

Modular Arithmetic

• a mod n = a − n⌊a/n⌋ (the remainder of a/n)
• 0 ≤ a mod n < n
• a ≡ b (mod n) means a and b have the same remainder when divided by n
• Equivalently, a ≡ b (mod n) ⟺ n divides (b − a)

Polynomials

A polynomial in n of degree d:

p(n) = Σᵢ₌₀ᵈ aᵢnⁱ, where aᵈ ≠ 0

• A polynomial is asymptotically positive iff aᵈ > 0
• For an asymptotically positive polynomial of degree d: p(n) = Θ(nᵈ)
• For any real constant a ≥ 0, nᵃ is monotonically increasing
• A function f(n) is polynomially bounded if f(n) = O(nᵏ) for some constant k

Exponentials

For all real a > 0, m, and n:

• a⁰ = 1, a¹ = a, a⁻¹ = 1/a
• (aᵐ)ⁿ = aᵐⁿ = (aⁿ)ᵐ
• aᵐ · aⁿ = aᵐ⁺ⁿ

Key facts:

• For all n and a ≥ 1, aⁿ is monotonically increasing in n
• Any exponential with base > 1 grows faster than any polynomial:

lim (n→∞) nᵇ/aⁿ = 0, so nᵇ = o(aⁿ) for all real constants a > 1, b

Properties of e (≈ 2.71828...):

• eˣ = 1 + x + x²/2! + x³/3! + ⋯ = Σᵢ₌₀^∞ xⁱ/i!
• eˣ ≥ 1 + x (equality only when x = 0)
• When |x| ≤ 1: 1 + x ≤ eˣ ≤ 1 + x + x²
• When x → 0: eˣ = 1 + x + Θ(x²)
• lim (n→∞) (1 + x/n)ⁿ = eˣ

Logarithms

Notation conventions:

• lg n = log₂ n (binary logarithm)
• ln n = logₑ n (natural logarithm)
• lgᵏ n = (lg n)ᵏ (exponentiation)
• lg lg n = lg(lg n) (composition)
• Logarithm functions apply only to the next term: lg n + k means (lg n) + k

Key identities (for a > 0, b > 0, c > 0, bases ≠ 1):

• a = b^(log_b a)
• log_c(ab) = log_c a + log_c b
• log_b aⁿ = n log_b a
• log_b a = log_c a / log_c b (change of base)
• log_b(1/a) = −log_b a
• log_b a = 1 / log_a b
• a^(log_b c) = c^(log_b a)

Important: Changing the base of a logarithm from one constant to another changes the value by only a constant factor — so we often use "lg n" in O-notation without specifying the base.

Series expansion for |x| < 1:

ln(1 + x) = x − x²/2 + x³/3 − x⁴/4 + ⋯

Inequalities for x > −1:

x/(1+x) ≤ ln(1+x) ≤ x (equality only for x = 0)

Polylogarithmic vs. polynomial: A function is polylogarithmically bounded if f(n) = O(lgᵏ n) for some constant k.

lgᵇ n = o(nᵃ) for any constant a > 0

Any positive polynomial grows faster than any polylogarithmic function.

Factorials

• n! = 1 · 2 · 3 · ⋯ · n (with 0! = 1)
• Weak upper bound: n! ≤ nⁿ

Stirling's approximation:

n! = √(2πn) · (n/e)ⁿ · (1 + Θ(1/n))

Key asymptotic results:

• n! = o(nⁿ)
• n! = ω(2ⁿ)
• lg(n!) = Θ(n lg n)

More precise form (for all n ≥ 1):

n! = √(2πn) · (n/e)ⁿ · e^(αₙ), where 1/(12n+1) < αₙ < 1/(12n)

Functional Iteration

f⁽ⁱ⁾(n) denotes f(n) applied iteratively i times:

• f⁽⁰⁾(n) = n
• f⁽ⁱ⁾(n) = f(f⁽ⁱ⁻¹⁾(n)) for i > 0

Example: if f(n) = 2n, then f⁽ⁱ⁾(n) = 2ⁱn.

The Iterated Logarithm Function

lg* n ("log star of n") — the number of times you need to take lg before the result drops to ≤ 1:

lg* n = min{ i ≥ 0 : lg⁽ⁱ⁾ n ≤ 1 }

This is an extremely slowly growing function:

Since the number of atoms in the observable universe is ≈ 10⁸⁰ (much less than 2⁶⁵⁵³⁶), we rarely encounter an input size n such that lg* n > 5.

Fibonacci Numbers

Defined by the recurrence:

• F₀ = 0, F₁ = 1
• Fᵢ = Fᵢ₋₁ + Fᵢ₋₂ for i ≥ 2

Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Golden ratio φ and its conjugate φ̂ are roots of x² = x + 1:

• φ = (1 + √5) / 2 ≈ 1.61803
• φ̂ = (1 − √5) / 2 ≈ −0.61803

Closed-form formula:

Fᵢ = (φⁱ − φ̂ⁱ) / √5

Since |φ̂| < 1, we have |φ̂ⁱ/√5| < 1/2, so:

Fᵢ = ⌊φⁱ/√5 + 1/2⌋ (nearest integer to φⁱ/√5)

Fibonacci numbers grow exponentially.