Sunday Function

Edit: The previous version of this post required some fixing, as I boneheadedly mixed up the O and Ω notations. The rest of it should still be good.

When you invest in stocks, bonds, mutual funds, or just about any other major investment vehicle, you’ll hear a standard but important disclaimer. “Past performance is not a reliable indicator of future returns.” And it’s wholly true. The hottest mutual fund of the last five years will very frequently revert to the mean over the next five. Or, start a Harley Davidson and an F-22 on the same runway and for the first few seconds the motorcycle will leave the jet in the dust. That performance doesn’t guarantee future results, and in a few more seconds the jet will pull ahead.

In mathematics and physics, we’re often not interested in what happens at the low end of a function. Very frequently for some f(x) or f(n), the x or n might represent huge quantum numbers or large numbers of atoms in a gas or lengthy time intervals compared to (say) the time of some underlying interaction. If we’re not interested in the small-x or small-n behavior of those functions, it’s also quite frequent that these functions can become much easier to deal with.

One of the ways to simplify the large-argument behavior of functions is called Big O notation. The slightly suggestive-sounding name comes from determining the order of a function for big values of the argument of that function. To define it, let’s take two functions “f” and “g”. We say that f is Ω(g(x)) if eventually f(x) is larger in magnitude than c*g(x) for every x larger than some critical value. Here “c” is some arbitrary constant.

Let’s do an example. Let f(x) = x and let g(x) = 1. Is f(x) = Ω(g(x))?

The equals sign is sort of an abuse of notation, we just use it as shorthand for the definition above. But let’s take a look at the question. For big x, is x > 1? Well sure, obviously. But we have to remember the arbitrary constant. What if it were equal to one million? It wouldn’t matter. For large enough x, x is greater than one million. The answer to our question is yes.

How about a harder one? Is this true?

Assume n is some constant natural number. In other words, we’re asking if (say), there some x such that e^x is thereafter greater than (say) 1,000,000*x^65,536. Or whatever other huge constants and exponents we want to name.

Well, probably the easiest way to think of it is in terms of the power series of e^x. But let’s try to figure out the answer without resorting directly to calculus. Start with the supposition that e^x > c*x^n. Take the logarithm of both sides:

Obviously (though we haven’t proved it so technically really this is just a plausible (though true) argument) log(x) is much more slowly growing than x, so large enough x will satisfy the requirement. Therefore e^x = Ω(x^n).

Which is very nice. All kinds of different functions have well defined big O relationships with each other. The polynomials are Ω of exponentials, exponentials are Ω of the factorial function, the factorial function is Ω of… well, not much in mathematical physics. In most cases it’s the fastest growing function we frequently encounter.

This is all very helpful. If we have (as we might in thermodynamics) a function that consists of a polynomial in the numerator and an exponential in the denominator, we know it will tend toward zero as x gets large. We know this without having to do any math, just because of the big O relationships. And I like it when math means I don’t have to do math.

1. #1 Joshua Zelinsky
October 18, 2009

This isn’t the standard notation. In the standard notation for O the f and g are reversed. See http://en.wikipedia.org/wiki/Big_O_notation

2. #2 Miko
October 18, 2009

As Joshua noted, you’ve got it backwards. The typical use of Big-O notation (in pure mathematics) is to get an idea of the size of the error in an approximation, and obviously we’re more interested in an upper bound for the error than a lower bound.

3. #3 Tony P
October 18, 2009

Nice hat tip to the maximum representation of a 16 bit number.

4. #4 Matt Springer
October 19, 2009

Y’all are right. We do these kinds of limits every day in physics, but as you know Big O notation as such is more of a computer science thing and isn’t actually used in physics that often. And so working from memory I wrote in the wrong variant. The “f(x) is asymptotically bigger than g(x)” concept uses capital omega. It’s fixed now. Thanks!

5. #5 Sam K.
October 19, 2009

the O() of some function is really a set, and it makes more sense to use the proper notation anyway (i.e. f is an element of O(g)). I never really understood why people use = instead.

6. #6 Joshua Zelinsky
October 19, 2009

Sam, it is for two reasons: One is historical (the notation was originally made that way) and the other is psychological. Like much good notation it is suggestive of what we can do with it (in that for most purposes we can treat that = like an actual = and get sensible results).