So let us practice the idea
of comparing two polynomials, for example, and
deciding whether or not they belong to the same class. So we define the class itself. In order to do it, we start with the idea of big-O notation, which is sometimes denoted is underlined o in
hand written text. The procedure here is as follows. Basically, assumes that we
have two of our functions as x squared and 5x
squared minus 100x. We, somehow, are talking about the upper boundary of one function with
regard to another. Basically, it means that
one function is greater no more than in some fixed number of times than the other one. In other words, we need to
write down an inequality here. Basically, assume that we
have some neighborhood of a given point, a, for example. We call one function big-O from another function
in this neighborhood. If there is some constant, positive constant, C
such as the relation, absolute value of the relation of functions f and g does not exceed this value c. So let us consider, for example, our case. We have x squared, for example, let us
call it f is x squared, g is 5x squared minus 100x and I'll assume that
x approaches infinity. So what we're going to
do, we're going to say, is that some function
is greater than the other in some
neighborhood of infinity. We need to write down something like the absolute value of f is less or equal some constant multiplied by absolute
value of g, all right? In other words, x squared
less or greater than some constant multiplied by Epsilon [inaudible] 5x
squared minus 100x. It's quite easy to
understand what constant is actually
good for us here. For example, let's start with the constant c, equal to one. Well, it's obvious that it is, because if we just assume
that c equals to one. Thus, we get x squared
on one side and 5x squares minus 100x
on the other side. If we subtract x squared from both sides, thus,
we get functions, which are clearly
positive from some point, because we are looking at a parabolic function
with positive. My coefficient, thus, there is a root and after this root, we do have only positive values. Thus, this inequality
holds and one. F is big-O towards G, that was one example. One code easily argues
that if we need to swap this function
that's still holds, just because instead of
writing c equals to one. Let us try to do
this interpret here. So basically, we need to prove
something, like this here. So in order to do each, we need to consider
another c naught, small one, but a great one. So basically, we start with
like c equals to five. Then we get a nice result here. But it's not always the
case, because, for example, let us look at some
more interesting case. For example, what does
[inaudible] functions, sine of x and x, as x approaches zero?
We do know what? They are basically equivalents
as one should expect, that sine x is
basically a big-O of x. It's quite easy, because the absolute value of
sine x, as we stated, whilst we were talking about
our second important limit, is now greater than model x, because the absolute value of x is actually the
area of the sector, and sine of x is the area of
the triangle respectively. So with that, we count that using a constant c equal to one, we get this absolutely right. But what if we substitute a
point of interest from zero, to let us say infinity? First of all, the
ideas that sine of x is big-O towards x, still holds at this very
point, because basically, sine of x is not greater than
one and x is the greatest. As you can imagine, x
approaches infinity. Thus, this inequality
still holds, for example, for the same
constant equal to one. But if we change it, if we change two functions, then we get 380, [inaudible] here, because sine x and x is not related in times. Because sine x is still, sorry, I have told you that we need to swap functions
and didn't do it. So it's a great deceit here. That is less deceitful. So x is big-O from sine of x. So basically, sine of x is bounded by one and minus
one and x is unbounded. Thus, if we tried to
come up with idea that x should be less
than some constant, multiplied by sine of
x and we say that this constant, for example, 10,000. So what's the error? Then we can for example, take x larger than two, since n, this equation, we will almost definitely just fall off and this is extremely not the case. It's not right. So when we are talking about
big-O notation, you always need to
consider the order here. What function, with regard to
what function? Is it big-O?