Question

1. (15 pts total) Prove or disprove each of the following claims, where f(n) and g(n) are functions on positive values.

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

(b) f(n) = O(g(n)) implies 2^f(n) = O(2^g(n))

(c) f(n) = O((f(n))^2)

Answer 1

(a)Given f(n) = O(g(n))

So for constant c and n0, we know that

f(n) ≤ c*g(n) where n>n0

As c>0, this can be rewritten as:

g(n) ≥ f(n)/c where n>n0

Let c1 = c, So

g(n) ≥ c1*f(n) where n>n0

Hence proved.

(b)

Given f(n) = O(g(n))

So for constant c and n0, we know that

f(n) ≤ c*g(n) where n>n0

Making this

2^f(n) ≤ 2^(c*g(n)) where n>n0

Let c1 = 2^c, So

2^f(n) ≤ c1*(2^g(n)) where n>n0

(c) Let f(n) = 1/n

if f(n) = O((f(n))^2)

So for constant c and n0, it should be:

1/n ≤ c*(1/n)^2 for n>n0

But this is not possible for any value of c as

1/n ≥ (1/n)^2

Hence this statement is false.