Question

Let f1 and f2 be asymptotically positive non-decreasing functions. Prove or disprove each of the following conjectures. To disprove, give a counterexample.

a.If f1(n) = Theta(g(n)) and f2(n) = Theta(g(n)) then f1(n) + f2(n) = Theta(g(n))

b.If f1(n) = O(g(n)) and f2(n) = O(g(n))then f1(n) = O(f2(n))

Answer 1

a) If f1(n) = Θ(g(n)) and f2(n) = Θ(g(n)) then  f1(n) + f2(n) = Θ(g(n))

This is TRUE.

According to the definition of big-theta if f1(n) = Θ(g(n)) then c1*g(n)<=f(n)<=c2*g(n) .............(1)

for some constants c1 and c2.

Similarly,

if f2(n) = Θ(g(n)) then c1'*g(n)<=f2(n)<=c2'*g(n) .............(2)

for some constants c1' and c2'.

If we add (1) and (2) we get:-

(c1+c1')g(n)<=f1(n) + f2(n)<=(c2+c2')g(n)...............(3)

Let c1+c1' = c1" and c2+c2' = c2"

Therefore, we can rewrite (3) as:-

c1"g(n)<=f1(n) + f2(n)<=c2"g(n)

Hence f1(n) + f2(n) = Θ(g(n))

b) .If f1(n) = O(g(n)) and f2(n) = O(g(n))then f1(n) = O(f2(n))

This is FALSE.

As a counterexample consider f1(n) = n² g(n) = n³ and f2(n) = n.

Here, f1(n) = O(g(n)) and f2(n) = O(g(n)) but f1(n) is not O(f2(n)) rather f2(n) = O(f1(n)).