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.