Asymptotic Notation Rigor: O, Ω, Θ, o, ω & Limit Laws

Formal Set-Theoretic Definitions & Relational Analogy

Let $f, g: \mathbb{N} \to \mathbb{R}_{\ge 0}$ be asymptotically non-negative functions. In CLRS notation, each asymptotic symbol defines a set of functions $f(n)$. Although we conventionally write $f(n) = O(g(n))$ as a macro shorthand, its formal mathematical meaning is set membership $f(n) \in O(g(n))$:

• Big-O ($O$, Asymptotic Upper Bound $\approx \le$): $O(g(n)) = \{ f(n) : \exists c > 0, \exists n_0 > 0 \text{ such that } \forall n \ge n_0, 0 \le f(n) \le c \cdot g(n) \}$.
• Big-Omega ($\Omega$, Asymptotic Lower Bound $\approx \ge$): $\Omega(g(n)) = \{ f(n) : \exists c > 0, \exists n_0 > 0 \text{ such that } \forall n \ge n_0, 0 \le c \cdot g(n) \le f(n) \}$.
• Big-Theta ($\Theta$, Asymptotically Tight Bound $\approx =$): $\Theta(g(n)) = O(g(n)) \cap \Omega(g(n))$. By the Transpose Symmetry & Dual Theorem, $f(n) \in \Theta(g(n)) \iff f(n) \in O(g(n)) \text{ and } f(n) \in \Omega(g(n))$.
• Little-o ($o$, Strictly Smaller Growth $\approx <$): Holds for all constants $c > 0$: $o(g(n)) = \{ f(n) : \forall c > 0, \exists n_0 > 0 \text{ such that } \forall n \ge n_0, 0 \le f(n) < c \cdot g(n) \}$. Equivalently, $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$.
• Little-omega ($\omega$, Strictly Larger Growth $\approx >$): Holds for all constants $c > 0$: $\omega(g(n)) = \{ f(n) : \forall c > 0, \exists n_0 > 0 \text{ such that } \forall n \ge n_0, 0 \le c \cdot g(n) < f(n) \}$. Equivalently, $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$.

Visualizing the Asymptotic Sandwich $\Theta(g(n))$ & Threshold $n_0$

Below $n_0$, lower-order terms and startup overheads allow $f(n)$ to cross wildly above or below $c_1 g(n)$ and $c_2 g(n)$. Once $n \ge n_0$, $f(n)$ is permanently trapped inside the cone $[c_1 g(n), c_2 g(n)]$.

Proving Asymptotic Relationships & Exposing Fallacies

Two mathematical pitfalls routinely trap engineers during complexity proofs:

1. Failure of Trichotomy: For real numbers $a, b$, exactly one of $a < b$, $a = b$, or $a > b$ holds. For functions, trichotomy fails! Consider $f(n) = n^{1 + \sin n}$, which oscillates infinitely between $1$ and $n^2$. Compared to $g(n) = n$, the ratio $f(n)/g(n) = n^{\sin n}$ has $\limsup = \infty$ and $\liminf = 0$, so $f(n)$ is neither $O(n)$ nor $\Omega(n)$.
2. One-Way Macro Equations & Unbounded Summations: In an equation like $2n^2 + 3n + 1 = 2n^2 + \Theta(n)$, any anonymous $\Theta(n)$ on the left-hand side can be absorbed into an anonymous $\Theta(n^2)$ on the right-hand side, never the reverse. Moreover, you cannot apply $\sum_{i=1}^{n} O(i) = O(n) \cdot O(n)$ blindly when the number of terms depends on $n$—you must sum the underlying series $\sum_{i=1}^{n} c \cdot i = c \frac{n(n+1)}{2} = \Theta(n^2)$ before taking the asymptotic class.

// C++20: Empirical Crossover Verification & Exact Harmonic / Stirling Asymptotic Bounds
#include <cmath>
#include <cstdint>
#include <numbers>

// Computes ln(n!) in O(1) time with relative error < 1/(12n) via Stirling's series:
// ln(n!) = n*ln(n) - n + 0.5*ln(2*pi*n) + 1/(12n) - 1/(360n^3) + O(1/n^5)
double stirlingLogFactorial(uint64_t n) noexcept {
    if (n <= 1) return 0.0;
    const double dn = static_cast<double>(n);
    const double invN = 1.0 / dn;
    return dn * std::log(dn) - dn
           + 0.5 * std::log(2.0 * std::numbers::pi * dn)
           + (invN / 12.0) * (1.0 - (invN * invN) / 30.0);
}

// Demonstrates why Sum_{i=1..n} floor(n / i) = Theta(n log n) (Sieve / Divisor Lattice)
uint64_t divisorLatticeWork(uint64_t n) noexcept {
    uint64_t ops = 0;
    for (uint64_t step = 1; step <= n; ++step) {
        for (uint64_t multiple = step; multiple <= n; multiple += step) {
            ++ops; // Executes floor(n / step) times; total = n * H_n = Theta(n log n)
        }
    }
    return ops;
}