Question about Big-O functions.

[reef]

I'm not really sure which section to post this in. I'm having trouble establishing witnesses for big-O functions. Basically I'm wondering if you are looking to solve the inequality for the lowest possible value of k, such that x > k.

Here's an example of what I'm talking about.

Eg. Determine whether f(x) is O(x^2) given the function f(x)=17*x+11.
|f(x)|<=C*|g(x)| where x>k.
|(17*x+11)|
=17*x+11
<=17*x+x where x>11
=18*x
<=x^2 where x>18
Therefore, f(x) is O(x^2) with witnesses C=1 and k=18.

My friend from class tells me that there are multiple correct solutions, but the answer given to me by my instructor is as follows:

|f(x)|<=17*x^2+11*x^2 where x>1
=28*x^2
Therefore, f(x) is O(x^2) with witnesses C=28 and K=1.

Any help/insight would be appreciated. This isn't a homework thread.

 

[Preno]

Why can't you just say that \lim_{x\to\infty} \frac{f(x)}{x^2} = 0?

 

[Landau]

Both answers are correct. It doesn't matter at all how sharp your estimates are. That's the point of big-O-notation: you only care about some limiting behaviour.

Preno's approach is equally valid, but I suspect that you haven't seen (or aren't allowed to use) this criterion.

 

[HallsofIvy]

I'm not really sure which section to post this in. I'm having trouble establishing witnesses for big-O functions. Basically I'm wondering if you are looking to solve the inequality for the lowest possible value of k, such that x > k.

Here's an example of what I'm talking about.

Eg. Determine whether f(x) is O(x^2) given the function f(x)=17*x+11.
|f(x)|<=C*|g(x)| where x>k.
|(17*x+11)|
=17*x+11
<=17*x+x where x>11
=18*x
<=x^2 where x>18
Therefore, f(x) is O(x^2) with witnesses C=1 and k=18.

Well, the problem is that f(x)= 17x+ 11 is NOT O(x^2). It is "o(x^2)" ("little o") which is what |17x+11|<= x^2 shows. But for "big O", you must also find k and C such that |x^2|<= C|17x+ 11| for x> k and that is impossible.

My friend from class tells me that there are multiple correct solutions, but the answer given to me by my instructor is as follows:

|f(x)|<=17*x^2+11*x^2 where x>1
=28*x^2
Therefore, f(x) is O(x^2) with witnesses C=28 and K=1.

Any help/insight would be appreciated. This isn't a homework thread.

Roughly speaking, to say that f(x)= O(g(x)) (as x goes to infinity) means that f and g have the same behaviour as x goes to infinity. And that can be determined by looking at
\lim_{x\to\infty} \frac{f(x)}{g(x)}
as Preno suggests.

If
\lim_{x\to\infty} \frac{f(x)}{g(x}}= 0
so that "f(x) goes to 0 faster than g(x)",
which is the case with f(x)= 17x+ 11 and g(x)= x^2, then f(x)= o(g(x)).

If that limit is some finite but non-zero number, so that "f(x) and g(x) go to 0 at the same rate", then f(x)= O(g(x)).

 

[Landau]

Well, the problem is that f(x)= 17x+ 11 is NOT O(x^2). It is "o(x^2)" ("little o") which is what |17x+11|<= x^2 shows. But for "big O", you must also find k and C such that |x^2|<= C|17x+ 11| for x> k and that is impossible.

I don't have much experience with these little and big O things, but it seems you are using a different definition than the one on wikipedia.

It says: f(x)= O(g(x)) as x->\infty iff there exists a K>0 and x0 such that |f(x)|\leq K|x^2| for all x>x0.

So you just have to find ONE K>0 such that this holds, while for little-o you must do this for EVERY K>0. So according to this definition it seems that certainly f(x)=O(x^2).

 

[reef]

Thanks for the replies. I've done quite a few exercises since I posted this and I think I've got it. In response to HallsofIvy, you're thinking of big-Omega which is defined as you said. There are three different types of these functions.

Big-O: f(x) is O(g(x)) if |f(x)|<=C*|g(x)| where x>k.

Big-Omega: f(x) is Ω(g(x)) if |f(x)|>=C*|g(x)| where x>k.

Big-Theta: f(x) is Θ(g(x)), if f(x) is O(g(x)) and g(x) is O(f(x)). Here you choose x>max(k1,k2).

I wish I knew how to type quantifiers and subscripts and what not. :P