# Growth of Functions

1. Mar 25, 2017

### emeraldskye177

1. The problem statement, all variables and given/known data

2. Relevant equations
Provided in (1).

3. 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...

Last edited: Mar 25, 2017
2. Mar 25, 2017

### Staff: Mentor

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.

3. Mar 25, 2017

### emeraldskye177

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.

4. Mar 25, 2017

### Staff: Mentor

But only in such a way that a constant can make it larger than f.
f>h does not rule out f in O(h).

You could test some functions to see if you find a counterexample.
Can you write down the two relevant relations (one given, one to show) explicitly? You should note a very similar structure.

5. Mar 25, 2017

### emeraldskye177

I must be missing something, but why wouldn't $\forall x > k ~~~ f(x) > h(x)$ mean $f \notin O(h)$?
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?

Last edited: Mar 25, 2017
6. Mar 25, 2017

### haruspex

Because it could also be the case that f(x)<2h(x) for x>k.
Yes. (I presume you are given c2>0.)

7. Mar 25, 2017

### emeraldskye177

$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).$

(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!

8. Mar 25, 2017

### Staff: Mentor

"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.

9. Mar 25, 2017

### emeraldskye177

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...

10. Mar 25, 2017

### Staff: Mentor

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