Problem 3. (10 points) Use the definition of big-Θ to show that f(n-6(g(n)) iff g(n)-Θ(f(n)).

** If you have any doubt then write to me in comment section.**

You can start from here:

Formal Definition: f(n) = Θ (g(n)) means there are positive constants c1, c2, and k, such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ k.

Because you have that iff, you need to start from the left side and to prove the right side, and then start from the right side and prove the left side.

Left -> right

We consider that:

f(n) = Θ(g(n)) 

and we want to prove that

g(n) = Θ(f(n)) 

So, we have some positive constants c1, c2and k such that:

0 ≤ c1*g(n) ≤ f(n) ≤ c2*g(n), for all n ≥ k 

The first relation between f and g is:

c1*g(n) ≤ f(n)     =>     g(n) ≤ 1/c1*f(n)    (1) 

The second relation between f and g is:

f(n) ≤ c2*g(n)     =>     1/c2*f(n) ≤ g(n)    (2) 

If we combine (1) and (2), we obtain:

1/c2*f(n) ≤ g(n) ≤ 1/c1*f(n) 

If you consider c3 = 1/c2 and c4 = 1/c1, they exist and are positive (because the denominators are positive). And this is true for all n ≥ k (where k can be the same).

So, we have some positive constants c3, c4, ksuch that:

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

which means that g(n) = Θ(f(n)).

Analogous for right -> left.