Definition
Asymptotic Equivalence
Two sequences
and (with for almost all ) are asymptotically equivalent, denoted , if their ratio approaches 1 as tends to infinity: Intuitively, this means that for sufficiently large
, the relative difference between and becomes negligible.
Properties
- Equivalence Relation: Asymptotic equivalence is reflexive (
), symmetric ( ), and transitive ( ). - Relation to Landau Notation: If
, then , meaning the error term is of smaller order than . - Multiplicativity: If
and , then .
Examples
- Polynomials:
. The lower-order terms become insignificant. - Factorials:
(Stirling’s approximation). - Logarithms:
.