Growth of Functions Homework | Solutions & Analysis

[emeraldskye177]

Homework Statement

[/B]

Homework Equations

Provided in (1).

The Attempt at a Solution

I think (a) is no because, though $c_1g > f,$ the actual un-vertically-translated $g$ could be less than $f,$ meaning its lower bound $c_2h < f$ over $c_2 \geq 1,$ meaning $h < f.$ Am I correct on this?

(b) I think the answer is yes. Am I correct in saying, if $f$ is $O(g),$ then $g$ is necessarily $Ω(f)$? But I'm not sure how to prove it...

 

[mfb]

I don't understand your argument for (a).
If the answer is "no", you can find an explicit counterexample. You don't have to provide it to solve the question, but that way you can be sure that you got it right.

(b) while that is right, it is the opposite of what you want to show.
The two equations given for the different cases look very similar, you can transform them into each other.

 

[emeraldskye177]

I don't understand your argument for (a).
If the answer is "no", you can find an explicit counterexample. You don't have to provide it to solve the question, but that way you can be sure that you got it right.

(b) while that is right, it is the opposite of what you want to show.
The two equations given for the different cases look very similar, you can transform them into each other.

Hi, thanks so much for replying! I'll try to explain my answer to (a) better. What I'm saying is:

$g$ can be less than $f$ for $\forall x \geq k,$ in which case $g$'s lower bound $c_2h$ must be less than $f$ for $\forall x \geq k'.$
If $c_2h < f$ then $f > h$ for $c_2 \geq 1$ so $f$ is not necessarily $O(h).$

For (b), I must admit I'm not sure where to begin w.r.t. transforming the equations into each other. We were not presented an example like this in class. Could you lend a bit more help here? Thanks so much again.

 

[mfb]

g can be less than f

But only in such a way that a constant can make it larger than f.

If $c_2h < f$ then $f > h$ for $c_2 \geq 1$ so $f$ is not necessarily $O(h).$

f>h does not rule out f in O(h).

Your approach won't work.
You could test some functions to see if you find a counterexample.

For (b), I must admit I'm not sure where to begin w.r.t. transforming the equations into each other. We were not presented an example like this in class. Could you lend a bit more help here? Thanks so much again.

Can you write down the two relevant relations (one given, one to show) explicitly? You should note a very similar structure.

 

[emeraldskye177]

f>h does not rule out f in O(h).

I must be missing something, but why wouldn't $\forall x > k ~~~ f(x) > h(x)$ mean $f \notin O(h)$?

Can you write down the two relevant relations (one given, one to show) explicitly? You should note a very similar structure.

When I tried your suggested approach, this is what I got:

I'm given $\forall x \geq k_2 ~~~ c_2h(x) \leq g(x),$ so by dividing by $c_2$ I arrive at $\forall x \geq k_2 ~~~ h(x) \leq c_3g(x)$ where $c_3 = 1/c_2.$

Is it that simple?

 

[haruspex]

I must be missing something, but why wouldn't $\forall x > k ~~~ f(x) > h(x)$ mean $f \notin O(h)$?

Because it could also be the case that f(x)<2h(x) for x>k.

I'm given $\forall x \geq k_2 ~~~ c_2h(x) \leq g(x),$ so by dividing by $c_2$ I arrive at $\forall x \geq k_2 ~~~ h(x) \leq c_3g(x)$ where $c_3 = 1/c_2.$
Is it that simple?

Yes. (I presume you are given c₂>0.)

 

[emeraldskye177]

Because it could also be the case that f(x)<2h(x) for x>k.

Yes. (I presume you are given c₂>0.)

Hi haruspex, thanks for replying.

(a) What I meant to say was this:

$g$ can be less than $f.$ Therefore, $g$'s lower bound $c_2h$ must be less than $f$ over $\forall x \geq k_2.$ Therefore, with $c = c_2$ and $k = k_2$ as witnesses, it is not necessarily the case that $f \in O(h).$

Therefore, my answer to (a) is no. Is my answer correct?

(b) So when the question asks for proof (values for witnesses), I would say the witnesses are $c = c_3 = 1/c_2$ and $k = k_2,$ correct?

Thanks!

 

[mfb]

$g$ can be less than $f.$ Therefore, $g$'s lower bound $c_2h$ must be less than $f$ over $\forall x \geq k_2.$

"Can be" does not imply "must be". And you have to rule out the existence of any constant to show that f is not in O(h). It is not sufficient to give one constant where the inequality might be violated.

Your approach won't work, no matter how long you try to fix holes.
Looking for a counterexample is much easier.

b: Right.

 

[emeraldskye177]

"Can be" does not imply "must be". And you have to rule out the existence of any constant to show that f is not in O(h). It is not sufficient to give one constant where the inequality might be violated.

Your approach won't work, no matter how long you try to fix holes.
Looking for a counterexample is much easier.

b: Right.

I meant $c_2h < f$ when $g < f$ after $x = k_2$ (which is the point at which $g > c_2h$). Sorry, I'm just trying to visualize the graphs in my head and think about the theory. I'm not sure how to come up with a counterexample...

 

[mfb]

For a counterexample: g is "larger than" in both comparisons. Just pick something growing very fast, then find f and h.