Thread: Witnesses for Big O

I am very lost right now when it comes to finding witnesses for big O relationships. The problem says the following:

To establish a big O relationship, find witnesses C and k such that
| f(x) | <= C | g(x) | whenever x > k


Determin whether each of these functions is O(x^2)

a) f(x) = 17x + 11

First of all, I am not sure if this is a O(x^2) function. I believe it is not because the function is not quadratic therefore it cannot be a O(x^2) function.

b) f(x) = x^2 +1000

This function is clearly a O(x^2) function. Now as for solving for C and k, I have no idea how to do.

I do not understand what is C and k, and what do they do.

Looking at "| f(x) | <= C | g(x) | whenever x > k"

f(x) is the function given
g(x) is the x^2 in "O(x^2)" right?

so for part b)

x^2 +1000 <= C(x^2)

now if k = 1 x>k so x can be 2 and that gives 1004 <= C*4
so C can be 251?


Thank you for your help!

Originally Posted by hotmail590

I am very lost right now when it comes to finding witnesses for big O relationships. The problem says the following:

To establish a big O relationship, find witnesses C and k such that
| f(x) | <= C | g(x) | whenever x > k


Determin whether each of these functions is O(x^2)

a) f(x) = 17x + 11

First of all, I am not sure if this is a O(x^2) function. I believe it is not because the function is not quadratic therefore it cannot be a O(x^2) function.

First if for some then , for all

In order to show that it is sufficient to find the witnesses.

Now lets find the witnesses. Lets assume , so now we seek
an such that:



Now just by sketching the two functions involved it is clear that if for some
then for all .

Now try , , and ,
so will do for for our witness .

RonL

Originally Posted by hotmail590

b) f(x) = x^2 +1000

This function is clearly a O(x^2) function. Now as for solving for C and k, I have no idea how to do.

I do not understand what is C and k, and what do they do.

Looking at "| f(x) | <= C | g(x) | whenever x > k"

f(x) is the function given
g(x) is the x^2 in "O(x^2)" right?

so for part b)

x^2 +1000 <= C(x^2)

now if k = 1 x>k so x can be 2 and that gives 1004 <= C*4
so C can be 251?

You need to show that:



for all with the value of you have choosen.
Now when , the LHS of the inequality is , and the
RHS is , which is less than the LHS if .

RonL

Thank you very much for your reply CaptainBlack!

Some questions I have:

For the first part a), I see that you have started by trying a value for k such as 1000 and then working your way to get C. Following your example, I tried to solve b) again. This time I used k as 1000 and came up with

| x^2 +1000| <= Cx^2 if x= 1001 then

1003001 < C(1002001)

and figured out C can be 100.

So I get k = 1000 and C = 100


Would it be also correct if C was any number larger than 100 such as 1000 or 10,000 or 99,999,999,999?


There are many differnt values for k and C for these types of problems (more than one answer) right?

Originally Posted by hotmail590

Thank you very much for your reply CaptainBlack!

Some questions I have:

For the first part a), I see that you have started by trying a value for k such as 1000 and then working your way to get C. Following your example, I tried to solve b) again. This time I used k as 1000 and came up with

| x^2 +1000| <= Cx^2 if x= 1001 then

1003001 < C(1002001)

and figured out C can be 100.

So I get k = 1000 and C = 100


Would it be also correct if C was any number larger than 100 such as 1000 or 10,000 or 99,999,999,999?


There are many differnt values for k and C for these types of problems (more than one answer) right?

Yes, that's right. The object is to find an example of a k and C that will
serve as witnesses, so we look for a case that is easy for us.

(You should also provide at least some explanation anout why the inequality
holds for any x>k -it being obviouse is ofen good enough )

RonL

Another question on the following problem:



http://i43.photobucket.com/albums/e3...0/untitled.jpg

What do those 2 symbols mean? The ones around the x's that look like half brackets



Many thanks again CaptainBlack for the help!

Originally Posted by hotmail590

Another question on the following problem:



http://i43.photobucket.com/albums/e3...0/untitled.jpg

What do those 2 symbols mean? The ones around the x's that look like half brackets



Many thanks again CaptainBlack for the help!

In case it's convenient here's the LaTeX for the above expressions:



-Dan

Originally Posted by topsquark

In case it's convenient here's the LaTeX for the above expressions:



-Dan

They are the floor and ceiling functions.

denotes the floor of , the greatest
integer less than .

denotes the ceiling of , the smallest
integer greater than .

RonL