Question

The O-notation

Answer 1

ye

Answer 2

show that \[f(x) = 5x ^{2}+ 2x+9\] is \[O(x ^{2})\]

Answer 3

well in the answer it says suppose x > 1

Answer 4

and then it says `then each of the terms in the polynomial f(x) is positive`
I never quite understood that either...

Answer 5

with x>1, x^2 will always be bigger than x,
when x is big the coefficients don't matter

Answer 6

for all x>1 we can write:
\[\frac{{5{x^2} + 2x + 9}}{{{x^2}}} = 5 + \frac{2}{x} + \frac{9}{{{x^2}}} \geqslant 5\]

Answer 7

then, by definition, we can write:
\[f\left( x \right) = O\left( {{x^2}} \right)\]

Answer 8

more explanation:
we have:
\[\mathop {\lim }\limits_{x \to + \infty } \frac{{5{x^2} + 2x + 9}}{{{x^2}}} = 5\]

Answer 9

so the ratio \[\frac{{5{x^2} + 2x + 9}}{{{x^2}}}\] is bounded

Answer 10

furthermore, we can write:
\[5 \leqslant \frac{{5{x^2} + 2x + 9}}{{{x^2}}} = 5 + \frac{2}{x} + \frac{9}{{{x^2}}} \leqslant 7\]

Answer 11

This is what the answer says

Suppose that x > 1. Then each of the terms in the polynomial f(x) is positive. Hence the absolute value of f(x) is given by the sum of the terms. Thus
\[\left| f(x) \right|=\left| 5x ^{2}+2x+9 \right|=5x ^{2}+2x+9\]
but \[x^{1}<x^{2}\] and \[x^{0}<x^{2}\]
Multiplying the first inequality by 2 and the second by 9, we have
\[2x^{1}<2x^{2}\] and \[9x^{0}<9x^{2}\]
Thus summing the terms we get
\[f(x)=sx^{2}+2x+9 < 5x^{2}+2x^{2}+(x^{2}=16x^{2}\]
Thus we have \[\left| f(x) \right|< 16 \left| x^{2} \right|\]

Answer 12

ok! Nevertheless if the ratio is bounded, then the subsequent limit:
\[\mathop {\lim }\limits_{x \to + \infty } \frac{{5{x^2} + 2x + 9}}{{{x^2}}}\]
has to be a finite quantity, as I shown above

Answer 13

where did the 7 come from?

Answer 14

because it will exist certainly an x value, say x_0, such that for all x Greater than x_0, the subsequently inequality holds:
\[5 \leqslant \frac{{5{x^2} + 2x + 9}}{{{x^2}}} = 5 + \frac{2}{x} + \frac{9}{{{x^2}}} \leqslant 7\]

Answer 15

for example we can pick x= 500

Answer 16

I'm sorry I'm not following...perhaps it might help if we start with what \[O(x ^{2})\] actually means.
What is it that I am trying to show here?

Answer 17

we can write:
\[f = O\left( g \right)\]
if we can find a constant K and a real number x_0, such that:
\[f\left( x \right) \leqslant Kg\left( x \right),\quad \forall x \geqslant {x_0}\]

Answer 18

where did the upside down A come from?

Answer 19

it is by definition

Answer 20

but your observation, namely:
\[\left| {f\left( x \right)} \right| \leqslant 16\left| {{x^2}} \right|\]
is good

Answer 21

ok so what does it mean?
the definition I have in front of me goes like this
|f(x)|<=M|g(x)| for all x>x0

Answer 22

\(\forall \) = for all

Answer 23

In my textbook, my definition doeesn't contain absolute values

Answer 24

nevertheless if:
\[\mathop {\lim }\limits_{x \to + \infty } \frac{{f\left( x \right)}}{{{x^2}}} < + \infty \]
then we can write:
\[f\left( x \right) = O\left( {{x^2}} \right)\]

Answer 25

O notation tends only to apply to non-negative increasing functions.

Answer 26

ok so since the upside down A means for all, that means I have the same definition, lets resume...you were telling me what the question was actually asking me to do (can you please say it in plain English, I never quite got the hang of the O-notation because of this unexplained fancy X in the textbook)

Answer 27

we have to found two objects, namely a constant K, and a real value x_0, such that:
for all x Greater than x_0, we have:
\[f\left( x \right) \leqslant Kg\left( x \right)\]

Answer 28

oops... we have to find...

Answer 29

so how is it that x < 1 is negative? shouldn't it be x < 0?

Answer 30

Basically, the idea is that as \(x\) gets larger and larger, the function \(f\) is less than the function \(g\) multiplied by some constant.

Answer 31

First just ignore the constant and consider the statement \[
f(x) \leq g(x)
\]For very large \(x\) values.

Answer 32

This is the general idea of big O notation. The constant doesn't actually change a lot. In fact this notation is called little o notation.

Answer 33

for example if x_0= 20, than we have:
\[\frac{{f\left( x \right)}}{{{x^2}}} = 5 + \frac{2}{x} + \frac{9}{{{x^2}}} \leqslant 5 + \frac{2}{{20}} + \frac{9}{{400}} = \frac{{2000 + 40 + 9}}{{400}} = \frac{{2049}}{{400}} = 5.1225\]

Answer 34

so we have x_0=20 and K=6

Answer 35

The purpose of \(x_0\) is to establish the fact that it's okay if \(f\) is greater than \(g\) early on, because it really only matters for very large \(x\) values.

Answer 36

so the question says show that
\[f(x)<x ^{2}\]
for large values of x ...is that it?

Answer 37

no, I don't think, I said another thing, please we have to apply the definition

Answer 38

how about lets understand the definition first, I think that is proving to be the biggest problem at the moment

Answer 39

we have to check this condition:
\[f\left( x \right) \leqslant Kg\left( x \right)\]
What is K? What is x_0?

Answer 40

The O notation was introduced in order to classify the behaviour of the real functions as x goes to infinity

Answer 41

Javk, do you understand limits?

Answer 42

kind of...just the basics

Answer 43

Do you remember the definition of a limit towards infinity?

Answer 44

That is as \(x\) approaches infinity?

Answer 45

Does this ring any bells?

Answer 46

Basically the definition of : \[
\lim_{x\to \infty}h(x) = L
\]Is defined as:

For all \(\epsilon\) there exists an \(N\) such that for all \(x\)\[
N\lt x\implies |h(x)-L|\lt \epsilon
\]

Answer 47

nope, sorry my bad, in that case I have no idea what limits are

Answer 48

Did you take calculus?

Answer 49

ok this is getting embarrassing...but no I don't think so, atleast not separately

Answer 50

Oh, usually you take Calculus at this point because it makes things easier.

Okay first of all, do you understand what it would mean to say:
For all \(x\) \[
f(x) \leq g(x)
\]

Answer 51

yeah...keep going

Answer 52

Okay, so do you understand what happens when we say:

For all \(x\gt x_0\) \[
f(x) \leq g(x)
\]

Answer 53

not really I don't quite know what the x_0 means, though I did understand before when you said it was there to establish that we ere only really considering larger values of x

Answer 54

Remember that \(x\) is a real number, so before it was still restricted such that: \[
-\infty \lt x \lt \infty
\]Now we are changing that to: \[
x_0 \lt x \lt \infty
\]

Answer 55

The \(x_0\) is going to be some number. It could be \(0\) or \(1\) or \(1000\). All we know is that \(x_0\) is some real number.

Answer 56

ok I'm following

Answer 57

You can think of a proof as a game between two players. One wants to prove the statement true, and the other wants to prove the statement false.

The "for all" variables are decided by the person trying to disprove the statement.

The "exists" variables are decided by the person trying to prove the statement.

Answer 58

In this case, the for all variable is \(x\).

The exists variables are \(x_0\) and \(c\).

There exists \(x_0\) and \(c\) such that for all \(x\)\[
x_0<x\implies f(x) \leq cg(x)
\]If \(x_0<x\) then \(f(x) \leq cg(x)\).

Answer 59

To better understand the definition let's just consider some examples...

Answer 60

It's beginning to make some sense now

Answer 61

Consider \(f(x) = x\) and \(g(x) = x+1\).
It's clear that for all \(x\)\[
f(x) \leq g(x)
\]If we let \(c=1\) then we can say: \[
f(x) \leq cg(x) = g(x)
\]
In this case, it doesn't even matter what \(x_0\) is.

Answer 62

how did you figure out what c was going to be?

Answer 63

I'll get more into \(c\) later. I'm going into \(x_0\) first.

Answer 64

ok..I'm following

Answer 65

Anyway, in this example I have given, there is no \(x_0\) we can give However, let's consider something a bit more complicated.

Suppose we let \(f(x) =x \) and \(g(x) = 1000\).
In this case we cannot say that for all \(x\) \[
f(x) \leq g(x)
\] This is because\[
x \leq 1000
\]is not true when \(x=2000\).

Answer 66

This is a case where it doesn't matter what we pick as \(x_0\) or as \(c\).
That is why \(x \neq O(1000)\)

Answer 67

The person will chose an \(x_0\) and some \(c\) to prove it.
This gives the inequality: \[
f(x) \leq cg(x) \\
x \leq 1000c
\]The disproving person gets to chose \(x\).
If we set \(x = 1000c + 1\), then the inequality will be false. The disproving person wins.

Answer 68

wait that last sentence got me

Answer 69

Let's consider another example
How about \(f(x) = x+1000\) and \(g(x) = x^2\)

Answer 70

What about the last sentence?

Answer 71

ok, no...I got it. Lets continue

Answer 72

Okay, so with this next example, if we consider \(x=0\), then we have: \[
f(x) = 1000 \not \leq 0 = cg(0)
\]It doesn't matter what \(c\) is, the inequality will not hold.

Answer 73

However if we choose a certain \(x_0\) value, then maybe we can get the inequality to hold.

Answer 74

If we set \(f(x) = cg(x)\), then we can find where the intersect, and finding the points of intersection allow us to find points where the inequality will hold.

Answer 75

However, we don't even have to be that rigorous. We could be lazy and just pick a super large \(x_0\) value, such as \(x_0=10000000\) if we wanted.

Answer 76

If we are to be rigorous, for the sake of understanding, then: \[
x+1000 = x^2\implies -x^2+x+1000 \implies x= \frac 12(1\pm \sqrt{4001})
\]So we can pick \(x_0 = \frac 12(1+\sqrt{4001})\)

But ultimately though, we could just say \(x=1000\)

Answer 77

so this shows how \(x_0\) affects this inequality.

Ultimately it means that it really doesn't matter what happens for small values of \(x\). We can always pick a bigger \(x_0\) to satisfy the inequality if we know \(f=O(g)\).

Answer 78

While \(x_0\) let's us chose a sort of "starting point", what \(c\) does is ultimately ignore any coefficients at play.

Answer 79

The best way to pick \(c\) is typically as the largest coefficient around or larger. It can only help the proving person to make \(c\) as large as possible.

Answer 80

For example, is the case of \(f(x) = 1000x^2 + 343x + 10\) and \(g(x) = x^2 \).

We might try \(c=1000\), that gives us: \[
1000x^2 + 343x + 10 \leq 1000x^2 =1000g(x)
\]This doesn't work well though. However we can find a \(c\) that works.

Answer 81

Consider \(c= 1001\). then we can say: \[
\underbrace{1000x^2+343x+10 \leq 1001x^2}_{-1000x^2} \implies 343x+10 \leq x^2
\]This will hold true if we allow \(x_0\) to be large enough.

Answer 82

So the \(c\) really just makes it so that coefficients do not matter and the \(x_0\) makes it so that only really large \(x\) matter.

Answer 83

So the point of big O is to compare functions after having stripped them of coefficients and for very large \(x\) values. It's used in computer science were \(x\) will represent something like the amount of data, such as the number of entries in a list.

Answer 84

Sorry... I lost my internet connection...thank you so much.
One more thing how would you read \(f(x)=5x ^{2}+2x+ 9\) is \(O(x ^{2})\)