info prev up next book cdrom email home

Asymptotic Notation

Let $n$ be a integer variable which tends to infinity and let $x$ be a continuous variable tending to some limit. Also, let $\phi(n)$ or $\phi(x)$ be a positive function and $f(n)$ or $f(x)$ any function. Then Hardy and Wright (1979) define

1. $f={\mathcal O}(\phi)$ to mean that $\vert f\vert<A\phi$ for some constant $A$ and all values of $n$ and $x$,

2. $f=o(\phi)$ to mean that $f/\phi\to 0$,

3. $f\sim\phi$ to mean that $f/\phi\to 1$,

4. $f\prec\phi$ to mean the same as $f=o(\phi)$,

5. $f\succ\phi$ to mean $f/\phi\to\infty$, and

6. $f\asymp\phi$ to mean $A_1\phi<f<A_2\phi$ for some positive constants $A_1$ and $A_2$.
$f=o(\phi)$ implies and is stronger than $f={\mathcal O}(\phi)$.


References

Hardy, G. H. and Wright, E. M. ``Some Notation.'' §1.6 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 7-8, 1979.




© 1996-9 Eric W. Weisstein
1999-05-25