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?