Question

1. Using the definition of Θ, prove that if f(n) ∈ Θ(g(n)), then g(n) ∈ Θ(f(n)).

Answer 1

To prove: if f(n) ∈ Θ(g(n)), then g(n) ∈ Θ(f(n)).

As we know that f(n) ∈ Θ(g(n)) implies that there are positive constants c1, c2, and k, such that Θ ≤ c1*g(n) ≤ f(n) ≤ c2*g(n) for all n ≥ k.
The first relation formed between f and g is:
c1*g(n) ≤ f(n) => g(n) ≤ 1/c1*f(n) ......equation(1)

The second relation between f and g is:
f(n) ≤ c2*g(n) => 1/c2*f(n) ≤ g(n) ......equation(2)

On combining both equation(1) and equation(2), we get:
1/c2*f(n) ≤ g(n) ≤ 1/c1*f(n)

let c3 = 1/c2 and c4 = 1/c1
since they exist and are positive(>=0) as c2 and c1 are positive which is true for all n>=k,
hence, we can derive that:

c3*f(n) ≤ g(n) ≤ c4*f(n), for all n ≥ k

Thus, g(n) ∈ Θ(f(n)), which is true;

Hence, if f(n) ∈ Θ(g(n)), then g(n) ∈ Θ(f(n))