How to prove a great relationship

Question

Hey, the name probably doesn't work a bit, so please correct it if you know which one is better.

As a homework, I was given several tasks:

Let f (n) and g (n) be asymptotically positive functions. Prove or disprove each of the following hypotheses.

a. f(n) = O(g(n)) implies g(n) = O(f(n))

Now, my real question is: how would you prove this formally? I know that the above would be easy, since I could easily provide a counter example to refute it, but for the sake of argument we can say that we want to do this without counter examples, because of course this goes on with some other examples, where it will not work.

I'm stuck a bit, I have the following inequalities written down (with <= less than or equal to)

f(n) <= c1 * g(n)
g(n) <= c2 * f(n)

But I’m not sure how to combine these 2 inequalities into a single (c) equation and refute it. I am pretty sure that this is something very simple that I just overlooked and that I'm pretty stupid now, but any pointers / concrete examples of how to do this would be great so that I can work the rest of these questions myself by oneself.

Answer 1

Why do you want to refute this without using a counterexample? This is the most direct way to refute a lawsuit.

If you had to prove it, of course, you could not use a counterexample. In this case, the inconsistency can work very well - suppose that the requirement is false, and then show how this leads to logical inconsistency.

f(n) <= c1 * g(n), , f(n) = O(g(n)). , g(n) <= c2 * f(n) f g ( , , , f g, ) , . : f g, , , c1 c2.

Answer 2

:
, f(n) = O(g(n)) , .

, O-:

• f(n) = O(f(n))
• c * O(f(n)) = O(f(n)), c
• O(f(n)) + O(f(n)) = O(f(n))
• O(O(f(n))) = O(f(n))
• O(f(n)) * O(g(n)) = O(f(n)g(n))
• O(f(n)g(n)) = f(n) * O(g(n))

( , 1 - -)