PROFESSOR: The issue of the approximate rate
at which things happen is a common in a lot of sciences,
the rate at which things fall, or the rate
at which reactions occur.
And in computer science, typical concern about growth rates
comes up in looking at the efficiency of algorithms,
and whether they're growing linearly, or quadratically,
or more.
And we're going to look today at four notations that
describe relations between the growth rates of functions.
The first of these relations is the simplest one.
It's called asymptotic equivalence,
or asymptotic equality.
So this is tilde symbol is read as asymptotically equal to.
So f of n is asymptotically equal to g of n,
if and only if the limit of the quotient of f of n over g of n
is 1.
Let's look at an example.
N squared is asymptotically equal to n squared plus n.
Why is that?
Well, it follows trivially by manipulating the algebra.
The limit of n squared plus n over n squared,
simplifying, is just the same as the limit of 1 plus 1 over n.
But as n goes to infinity, 1 over n
goes to 0, so the limit is 1 as claimed.
Those two expressions, or the functions they define,
n squared and n squared plus 1 are asymptotically equal.
So there's some easy properties of asymptotic equality
that follow immediately from the definition.
One of them is that it's symmetric,
namely, suppose that f is asymptotically equal to g.
I want to prove that g is asymptotically equal to f.
Well, what's going on here?
Let's look at the limit of g over f, which
is what I'd like to prove as 1.
Well, the limit of g over f, by algebra, g over f
is the same as 1 over f over g, so just moving a limit
across the division, that's the same as 1
over the limit of f over g, which is 1 over 1.
And we've proved in other words, the g
is asymptotically equal to f, given that f is asymptotically
equal to g.
It's symmetric.
There's a similar argument for transitivity.
Let's just crank through it for practice on the definition.
Suppose that f is asymptotically equal to g,
and g is asymptotically equal to h,
I'd like to prove that f it's asymptotically equal to h.
Well, again, we just plug into the algebra
and distribute limits.
Let's just look at this.
We're given that 1 is the limit of f over g,
because f is asymptotic to g.
But f over g can be expressed as f over h divided by g over h.
That's just algebra.
The h's cancel.
So this limit, now, I can distribute the limits
to the numerator and denominator,
assuming both exist, and the numerator limit
is what I'm interested in.
The denominator limit is going to be 1,
because the limit of g over h is 1.
Since g is asymptotically equal to h,
the conclusion is indeed that the limit of f over h
is equal to 1.
This is not really very interesting stuff,
and the top level message is that
many of these elementary properties
of asymptotic equality and the other asymptotic relations
that we're going to see follow by this kind
of elementary algebra, and distributing the limits
over sub expressions.
Anyway, the corollary of this is that asymptotic equality
is in fact an equivalence relation.
We've proved it's symmetric and transitive,
and it's trivially reflexive.
It's an equivalence relation.
By the way, it's worth noting that it's
an equivalence relation on functions of one variable, when
we write sometimes that f of n is asymptotically
equal to g of n.
But we mean that f of n is the description of the function f.
We're not talking about the number that f of n
happens to have for some particular value of f.
So we'll sometimes write f of n is
asymptotically equal to g of n.
For descriptive purposes, the proper thing
we should be writing is that f is asymptotically equal to g.
Asymptotic equality is a relation between functions.
OK.
The next asymptotic relation we're going to look at
is called asymptotically smaller than, and the notation for it
is this little o notation.
So you'd write that f of n is equal to little o of g of n,
if and only if the limit of f of n over g of n goes to 0 as n'
approaches infinity.
So let's look at an example of that.
N squared is little o of n cubed,
because trivially, the limit of n squared over n cubed
is the same as the limit of 1 over n.
It's equal to zero.
And by similar kind of reasoning that we
did for asymptotic equality being an equivalence relation,
it's not very hard to prove that little o defines
a strict partial order on functions.
So the third asymptotic relation is the most complicated
of the three.
It's arguably the most important in computer science.
It's called the asymptotic order of growth, o.
And the definition is that if function
f is big o of a function g, what it means
is that the limit of f over g is finite.
So it might be other than 0 or 1, but it's finite.
And that means that f is big o of g.
Now, there's a technicality there
where the expression actually says the limsup of f of n
over g of n.
Let's just ignore that for now, and we'll look at it
and explain why the limsup is there a little later.
So as an example, 3n squared is big o
of n squared, because the quotient of 3n
squared over n squared is 3, which is less than infinity.
So what big o is doing is kind of saying that constant factors
don't matter.
And that turns out to be particularly useful in computer
science, where you can't really talk about the time
that a procedure takes, because that's going
to depend on the hardware.
So when you implement it on faster hardware,
it may grow at the same rate, but the time
will actually change.
And that's why big o plays a prominent role.
The final relation of the four is called
theta, or same order of growth.
The definition of f is theta of g
is simply that f is o of g and g is o of f.
And it's easy to show from the definition
that theta is an equivalence relation.
So to summarize, there are these four relations.
F asymptotically equal to g means informally
that f and g are nearly equal.
F equals little o of g informally means
that f is much less than g.
F equals o of g means that f is roughly less
than or equal to g, where roughly
means that we're not concerned about constant factors.
And f equals theta of g means that f is roughly equal to g.
And we'll examine these properties
in more detail in the next segment.