we say that f has order at most g. We write this as
If
then f has order at least g, for which we use
Finally, if there exist constants c 1 and c 2 such that
f and g have the same order of magnitude, expressed as
In this order-of-magnitude notation, we ignore multiplicative constants and
lower-order terms that become negligible as n increases.
Example 1.3
Let
Then