Asymptotic Equivalence

Definition

Asymptotic Equivalence

Two sequences $(a_{n})_{n \in N}$ and $(b_{n})_{n \in N}$ (with $b_{n} \neq = 0$ for almost all $n$ ) are asymptotically equivalent, denoted $a_{n} \sim b_{n}$ , if their ratio approaches 1 as $n$ tends to infinity:
$a_{n} \sim b_{n} ⟺ n \to \infty lim \frac{a _{n}}{b _{n}} = 1$
Intuitively, this means that for sufficiently large $n$ , the relative difference between $a_{n}$ and $b_{n}$ becomes negligible.

Properties

Equivalence Relation: Asymptotic equivalence is reflexive ( $a_{n} \sim a_{n}$ ), symmetric ( $a_{n} \sim b_{n} ⟺ b_{n} \sim a_{n}$ ), and transitive ( $a_{n} \sim b_{n} \land b_{n} \sim c_{n} ⟹ a_{n} \sim c_{n}$ ).
Relation to Landau Notation: If $a_{n} \sim b_{n}$ , then $a_{n} = b_{n} + o (b_{n})$ , meaning the error term is of smaller order than $b_{n}$ .
Multiplicativity: If $a_{n} \sim b_{n}$ and $c_{n} \sim d_{n}$ , then $a_{n} c_{n} \sim b_{n} d_{n}$ .

Examples

Polynomials: $n^{2} - n \sim n^{2}$ . The lower-order terms become insignificant.
Factorials: $n! \sim (\frac{n}{e})^{n} 2 πn$ (Stirling’s approximation).
Logarithms: $lo g (n!) \sim n lo g n$ .

Lukas' Notes

Asymptotic Equivalence

Definition

Properties

Examples

Graph View

Table of Contents

Backlinks