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.