📚 Big O Notation: A Comprehensive Guide

• Main Topics Covered:
  • Foundational concepts and historical context of Big O notation
  • Formal definitions for general, infinite, and finite domains, including set-based interpretations
  • Practical examples across infinite, finite, and multivariate domains
  • Core mathematical properties and algebraic manipulation rules
  • Comparative growth rates of functions (polynomials, logarithms, and exponentials)
  • Advanced usage and specialized notations

---

💡 Core Concepts and Background

Big O notation is a mathematical notation that describes the approximate size of a function on a domain. It is part of the Bachmann–Landau notation family, originally invented by German mathematicians Paul Bachmann (1894) and Edmund Landau (1909), with earlier contributions by Paul du Bois-Reymond (1870).

• The letter O stands for Ordnung, meaning the order of approximation.
• Upper bound: A description of a function using Big O notation only provides an upper bound on its growth rate.

Applications Across Fields

• Computer Science: Classifies algorithms by how their run time or space requirements grow relative to the input size.
• Analytic Number Theory: Expresses bounds on the growth of arithmetical functions (e.g., remainder terms in the prime number theorem).
• Mathematical Analysis (Calculus): Bounds errors when truncating power series and expresses the quality of approximation of functions by simpler functions.

Related Notations

Several related symbols describe different kinds of bounds on growth rates:

• $o$ (little-o)
• $\sim$ (asymptotic equivalence)
• $\Omega$ (Big Omega - lower bound)
• $\ll$ (Vinogradov notation)
• $\gg$
• $\asymp$ (asymptotic tightness)
• $\omega$ (little omega)
• $\Theta$ (Theta - tight bound)

---

📐 Formal Definitions

1. General Definition

Let $f$ be a real or complex-valued function defined on a domain $D$, and let $g$ be a non-negative real-valued comparison function on the same domain $D$.

We write: $f(x) = O(g(x))$

Read as: "$f(x)$ is big $O$ of $g(x)$" if there exists a positive real number $M$ (called the implied constant) such that: $|f(x)| \leq M \cdot g(x) \quad \text{for all } x \in D$

If $g(x) > 0$ throughout $D$, an equivalent definition states that the ratio $\frac{f(x)}{g(x)}$ is bounded; that is, there is a positive real number $M$ such that: $\left|\frac{f(x)}{g(x)}\right| \leq M \quad \text{for all } x \in D$

Note: The equality sign ($=$) does not represent strict mathematical equality, but rather an inequality relating $f$ and $g$. Vinogradov introduced the alternative notation $f \ll g \iff f = O(g)$.

2. Asymptotic Definitions ($x \to \infty$ or $x \to a$)

• As $x \to \infty$: For functions eventually positive on $[a, \infty)$: $f(x) = O(g(x)) \quad \text{as } x \to \infty$ means that for some real number $a$, $f(x) = O(g(x))$ holds on the domain $[a, \infty)$.
• In a neighborhood of $a$: $f(x) = O(g(x)) \quad \text{as } x \to a$ means that for some constant $c > 0$, $f(x) = O(g(x))$ holds on the interval $[a-c, a+c]$.
• Error terms: $f(x) = h(x) + O(g(x)) \implies f(x) - h(x) = O(g(x))$

3. Set Version of Big O

In computer science, $O(g(x))$ often represents the set of all functions $\tilde{f}$ that satisfy $\tilde{f}(x) = O(g(x))$. This is written as: $f(x) \in O(g(x))$ Read as: "The function $f(x)$ is among the set of all functions of order at most $g(x)$."

---

📊 Practical Examples

Infinite Domain Examples (Large $x$)

When analyzing behavior for very large $x$, terms that grow most quickly dominate.

• Sum Rule: Keep the term with the highest growth rate; omit all others.
• Product Rule: Omit any constant factors that do not depend on $x$.

Detailed Example: Let $f(x) = 6x^4 - 2x^3 + 5$ and $g(x) = x^4$. To prove $f(x) = O(x^4)$ for $x \geq 1$: $|6x^4 - 2x^3 + 5| \leq 6x^4 + |-2x^3| + 5 \leq 6x^4 + 2x^4 + 5x^4 = 13x^4$ Choosing $M = 13$ satisfies $|f(x)| \leq 13x^4$ for all $x \geq 1$. (Note: $O(x^{10})$ is a valid upper bound but less precise; $O(x^3)$ is false).

Finite Domain Examples

On finite intervals, error terms in function approximations are summarized using Big O. For example, using Taylor's theorem for small $x$:

• $e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dotsb \quad (\text{for all finite } x)$
• $e^x = 1 + x + \frac{x^2}{2} + O(|x|^3) \quad (\text{for all } |x| \leq 1)$
• $e^x = 1 + x + O(x^2) \quad (\text{for all } |x| \leq 1)$

Domain behavior can drastically change outcomes. For instance:

• $(x+1)^8 = x^8 + O(x^7) \quad (\text{for } x \geq 1)$
• $(x+1)^8 = 1 + 8x + O(x^2) \quad (\text{for } |x| \leq 1)$

Multivariate Examples

Expression	Domain Constraints	Interpretation
$x \sin y = O(x)$	$x \ge 1, y \in \mathbb{R}$	Bound is uniform across variables.
$\frac{xy}{x^2+y^2} = O(1)$	Real $x, y$ (not both $0$)	Any bounded function is $O(1)$.
$(x+y)^{10} = O(x^{10})$	$x \ge 1, -2 \le y \le 2$	Mix of finite and infinite domains.
$(1+x)^b = 1 + O_b(x)$	$0 \le x \le 1, b \in \mathbb{R}$	Implied constant $M_b$ depends on parameter $b$.

---

⚙️ Algebraic Properties

Operation	Rule
Product	$f_1 = O(g_1) \text{ and } f_2 = O(g_2) \implies f_1 f_2 = O(g_1 g_2)$ $f \cdot O(g) = O(\|f\|g)$
Sum	$f_1 = O(g_1) \text{ and } f_2 = O(g_2) \implies f_1 + f_2 = O(\max(g_1, g_2))$ If $f_1 = O(g)$ and $f_2 = O(g)$, then $f_1 + f_2 = O(g)$.
Constant Multiplication	For nonzero constant $k$: $O(\|k\| \cdot g) = O(g) \implies k \cdot f = O(g)$
Transitive Property	If $f = O(g)$ and $g = O(h)$, then $f = O(h)$.

---

📈 Growth Rate Hierarchies Toward Infinity

When analyzing polynomial, logarithmic, and exponential expressions as $n \to \infty$, specific domination rules apply:

1. Large powers dominate small powers: For $b \ge a$, $n^a = O(n^b)$ as $n \to \infty$.
2. Powers dominate logarithms: For any positive $a, b$, $(\log n)^a = O_{a,b}(n^b)$, regardless of how large $a$ is or how small $b$ is.
3. Exponentials dominate powers: For any positive $a, b$, $n^a = O_{a,b}(e^{bn})$.

Terminology Classifications

• Superpolynomial: Grows faster than $n^c$ for any $c$.
• Subexponential: Grows more slowly than any exponential function $c^n$ ($c > 1$).
• Note on Logarithms & Bases: Powers of $n$ inside logarithms can be ignored (e.g., $O(\log n) = O(\log(n^c))$). Logs with different constant bases are equivalent, whereas exponentials with different bases ($2^n$ vs $3^n$) are not of the same order.