ALBERT R. MEYER: Let's take a quick look at some blunders that people regularly make in dealing with asymptotic notation, in particular with big O notation, which tends to confuse people. So the most important thing to remember is that this notation, something equals O of something else-- 1/x equals O of 1, say-- is actually to be understood as just a not such attractive notation, misleading notation for a binary relation between two functions. This is supposed to be a function there, and this is supposed to be a function there. And this is saying that there's a relation between the growth rates of these two functions.
O of f is not quantity. And you mustn't treat it as such. So, for example-- and the equality, of course, is not an inequality. Once upon a time, we tried to get the equality replaced by an epsilon, which makes much better sense-- that is, a membership symbol. But there was a sense that this notation was so deeply embedded in the mathematical culture-- multiple mathematical communities-- that there was no way we were going to change it.
In particular, a confusion where you think that that equality sign means some kind of an equality is to write instead of f equals O of g, well, if f equals O of g by symmetry, O of g ought to equal f. Don't write that. The reason is that it's a recipe for confusion, because look at this. I know that x is O of x trivially, which would suggest that O of x is equal to x, if you believe in symmetry and you think of O of x as being quantity.
Well, remember, though, that 2x is also equal to O of x by definition of O. So what we wind up with is combining 2x equals O of x with O of x equals x is I get 2x is equal to this thing, is equal to x. I conclude that 2x is equal to x, which is absurd. So that's nonsense. It's the kind of trouble that you can get into if you start thinking of this equality as meaning equality between two quantities, as opposed to just being a part of the name of a relation.
Another mistake that people make is less serious but it's sloppy, is to think that big O corresponds to a lower bound, so that people will say things like f is at least O of n squared. Well, again, at least O of n squared is starting to treat O of n squared like a quantity. You could say that f is equal to O of n square, but that means that n squared is an upper bound on f to within a constant factor after a certain point. If you want to say intuitively that n squared is a lower bound on f, then all you have to do is say that n squared is O of f. And that is a proper use of O of f of getting a lower bound on a function, by saying that the lower bound is O of the function.
Another example of the kind of nonsense that you see-- this is a stretch, but let's look at it as a reminder of things not to do. I'm going to prove to you that the sum from i equals 1 to n of i-- that is that 1 plus 2 plus 3 up to n-- is O of n. Now, of course, it's not. We know that the sum of the first n integers n times n plus 1 over 2, which is O of n squared-- theta of n squared actually. So I'm going to prove something false. Watch carefully how I do it.
Here's the false proof. Let's, first of all, notice that any constant is O of 1. So 0 is O of 1, 1 is O of 1, 2 is O of 1, and so on. Any constant function is O of the constant function 1. OK, that's true.
So that means that each i in this sum, i is a number, so that means it might be 1, it might be 2, it might be 3, it might be 50. Whatever it is, it's O of 1. And that means that I could think of this sum from i equals 1 to n as O of 1 plus O of 1 plus O of 1. And that's, of course, n times O of 1, which is O of n.
Now, there's all kinds of weird arithmetic rules of things being used here, none of which are justified. But it's just a heads up. You do see stuff like this from inexperienced students. And I hope that you won't fall into this kind of a sloppy trap. O of something is not a quantity. It's part of the name of a relation.