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

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

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

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

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

Now try \$\displaystyle x_0=1,000\$, \$\displaystyle x_0^2=1,000,000\$, and \$\displaystyle 17x_0+11=17,011\$,
so \$\displaystyle 1,000\$ will do for for our witness \$\displaystyle 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:

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

for all \$\displaystyle x>1\$ with the value of \$\displaystyle C\$ you have choosen.
Now when \$\displaystyle x=1.1\$, the LHS of the inequality is \$\displaystyle 1001.21\$, and the
RHS is \$\displaystyle C(1.1)^2\$, which is less than the LHS if \$\displaystyle 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:
\$\displaystyle \lfloor x \rfloor\$
\$\displaystyle \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:
\$\displaystyle \lfloor x \rfloor\$
\$\displaystyle \lceil x \rceil\$

-Dan

They are the floor and ceiling functions.

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

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

RonL