Discrete Structures and Big O Notation.

[Unity+]

The problem is asking the following:

Determine if the following function is O(x^2).

 

f(x) = 17x+11

 

I attempted the problem by doing the following:

 

Since the highest degree is 1, the following function is valid. Now, let's set c = 17.

 

17x + 11 <= 17x^2

 

x + (11/17) <= x^2

 

Since x = 2 is the lowest natural number that makes the statement true, c = 17 and k = 2.

 

Is this done right?

[John]

Depending on what exactly your instructor expects, this may be a valid answer.

However, a couple of things:

1. Formally, using the definition, the statement is true, but is O(x²) the tightest bound?

 

2. Keep in mind that c and k aren't restricted to being natural numbers. I mention this only because it seems like you're looking for the smallest values.

Edited March 11, 2015 by John

[studiot]

Why did you choose C = 17?

 

Proving the statement

[math]17x + 11 = O({x^2})[/math]

means find a C and k such that

[math]\left| {17x + 11} \right| \le C{x^2}:\left| x \right| \ge k[/math]

 

Echoing what John said, I am not sure why you included discrete in the title?

 

For discrete structures we usually use n as the variable. x usually refers to real numbers in which case the inequality would be true for all x except within an interval determined by C an k. If x was complex then it would all x outside some disk of radius k, as John says.

[Unity+]

Depending on what exactly your instructor expects, this may be a valid answer.

 

However, a couple of things:

 

1. Formally, using the definition, the statement is true, but is O(x²) the tightest bound?

 

2. Keep in mind that c and k aren't restricted to being natural numbers. I mention this only because it seems like you're looking for the smallest values.

The teacher stated that any number works, since k and c are simply "witnesses" to whether O(g(x) represents the function.

 

The problem was just asking for O(x^2).

 

Thanks for the help, btw.