same order of magnitude

Roughly, two functions have the same order of magnitude if each one is bounded by a constant times the other. More precisely, f(x) and g(x) have the same order of magnitude if f(x) = O(g(x)) and g(x) = O(f(x)). For example: x+7 and 34x have the same order of magnitude; as do x + log(x) and x; but x7 and x9 do not.

If f and g are asymptotically equal, then they have the same order of magnitude. The converse is not true.

See Also: BigOh, LittleOh

Printed from the PrimePages <primes.utm.edu> © Chris Caldwell.