# Witnesses for Big O

• Mar 9th 2006, 08:54 PM
hotmail590
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?

• Mar 9th 2006, 10:44 PM
CaptainBlack
Quote:

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 $f(x)=O(x^n)$ for some $n$ then $f(x)=O(x^m)$, for all $m\ge n$

In order to show that $f(x)=O(x)$ it is sufficient to find the witnesses.

Now lets find the witnesses. Lets assume $C=1$, so now we seek
an $k$ such that:

$
|17x+11|\le|x^2|\ \forall\ x>k
$

Now just by sketching the two functions involved it is clear that if for some
$x_0>0,\ x_0^2>17x_0+11$ then $x^2>17x+11$ for all $x>x_0$.

Now try $x_0=1,000$, $x_0^2=1,000,000$, and $17x_0+11=17,011$,
so $1,000$ will do for for our witness $k$.

RonL
• Mar 9th 2006, 11:02 PM
CaptainBlack
Quote:

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:

$
x^2+1000 \le C x^2
$

for all $x>1$ with the value of $C$ you have choosen.
Now when $x=1.1$, the LHS of the inequality is $1001.21$, and the
RHS is $C(1.1)^2$, which is less than the LHS if $C=251$.

RonL
• Mar 10th 2006, 03:23 PM
hotmail590

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?
• Mar 10th 2006, 09:12 PM
CaptainBlack
Quote:

Originally Posted by hotmail590

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
• Mar 10th 2006, 09:45 PM
hotmail590
Another question on the following problem:

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

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!
• Mar 11th 2006, 04:31 AM
topsquark
Quote:

Originally Posted by hotmail590
Another question on the following problem:

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

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:
$\lfloor x \rfloor$
$\lceil x \rceil$

-Dan
• Mar 11th 2006, 05:57 AM
CaptainBlack
Quote:

Originally Posted by topsquark
In case it's convenient here's the LaTeX for the above expressions:
$\lfloor x \rfloor$
$\lceil x \rceil$

-Dan

They are the floor and ceiling functions.

$\lfloor x \rfloor$ denotes the floor of $x$, the greatest
integer less than $x$.

$\lceil x \rceil$ denotes the ceiling of $x$, the smallest
integer greater than $x$.

RonL