Question

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

   1. f(n) = O(g(n)) implies g(n) = Ω(f(n)) .
   2. f(n) = O(g(n)) implies g(n) = O(f(n)).
   3. f(n) + g(n) = Θ(min(f(n),g(n))).

Answer 1

(a) True

Proof:

By definition as f(n)=O(g(n)), there exists constant c such that f(n) <=c*g(n).

So, g(n) >= (1/c)f(n)=c1*f(n).

Hence ,

(b) False:

Proof:

Let's prove this by counter example.

Let f(n)=n and g(n)=n².

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

But, we can not find any constant c such that g(n)<=c*f(n).

Hence, g(n)=O(f(n)) is false.

(c) False:

Proof:

Let's prove this also by counter example.

Let f(n)=n and g(n)=n².

Now, min (f(n)+g(n))=n.

f(n)+g(n)=n+n²>=c*n, for c=1.

Hence,

But, we can not find any constant c1 such that, f(n)+g(n)=n+n²<=c1*n.

Hence, f(n)+g(n)=O(min(f(n),g(n)) is not true.

As, by definition of for , we have to prove

Hence, is false.