asymptotically equal
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000:
GIMPS has discovered a new largest known prime number: 282589933-1 (24,862,048 digits)

One way of saying that two functions f(x) and g(x) are about the same size is to say that they are asymptotically equal: Two functions f(x) and g(x)are asymptotically equal (as x approaches infinity) if the following limit holds:

The limit of f(x)/g(x) (as x approaches infinity) is one
This is often denoted f(x)~ g(x). For example: 3x4+2x+7 ~ 3x4, x+sin x ~ x, and the prime number theorem states that pi(x) ~ x/log x.

If f(x)~g(x), then f is O(g) and g is O(f), but the converse is not true. Equivalently, if f(x)~ g(x), then g has the same order of magnitude as f (and again the converse is false). Finally, if f(x)~ g(x), then f(x)- g(x) is o(g(x)).

See Also: BigOh, LittleOh

Chris K. Caldwell © 1999-2019 (all rights reserved)