proof 0 (f (n)) = 0 (g(n)) if and only if f (n) E 0 (g(n)) and g(n) E O (f (n))

85 Views Asked by At

The problem :

For arbitrary functions f and g : IN -> IR*, prove that
  1. O(f (n)) = O(g(n)) if and only if f ( n ) ∈ O ( g ( n ) ) and g ( n ) ∈ O ( f ( n ) ) .

I tried to do it by definition :

So given f ( n ) ∈ O ( g ( n ) ) and g ( n ) ∈ O ( f ( n ) ) .

 ∃ C1>0 ,∃ n1>0 so that for all n> n1 , f(n) ≤ C1*g(n).

 and

 ∃ C2>0 , ∃ n2>0 so that for all n> n2 , g(n) ≤ C2*f(n).

 so for n'=max(n1,n2) => f(n) ≤ C1*g(n) and g(n) ≤ C2*f(n)

but i don't understand how to continue,i tried to start from the other side but without success.

How can this claim be proven by definition?