Asymptotic notation

Asymptotic notation

A relation related to little-o is the asymptotic notation ${\displaystyle \sim }$. For real valued functions ${\displaystyle f,g}$, the expression $${\displaystyle f(x)\sim g(x)\quad {\text{ as }}x\to \infty }$$ means $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=1.}$$ One can connect this to little-o by observing that ${\displaystyle f(x)\sim g(x)}$ is also equivalent to ${\displaystyle f(x)=(1+o(1))g(x)}$. Here ${\displaystyle o(1)}$ refers to a function tending to zero as ${\displaystyle x\to \infty }$. One reads this as "${\displaystyle f(x)}$ is asymptotic to${\displaystyle g(x)}$". For nonzero functions on the same (finite or infinite) domain, ${\displaystyle \sim }$ forms an equivalence relation.