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.