If f(n) = θ(g(n)), and for every , (),()≥ 2 then log(f(n)) = θ(log(g(n)))?

user_17248975 0
Viewed 459

Is this statement false? I couldn't find a answer to this question in this site (only for big O).

from the definition i can assume: log⁡(C1g(n)) ≤ log⁡(f(n)) ≤ log⁡(C2g(n))

i solved the right side: log⁡(f(n)) ≤ log⁡(C2g(n)) ≤ log⁡(C2) + log⁡(g(n)), Because log⁡(g(n))>1, there is C2log⁡(g(n)) ≥ log⁡(C2 ) => log⁡(f(n)) ≤ C2log⁡(g(n)) + log⁡(g(n)) ≤ (C2+1)log⁡(g(n)).

but i couldn't find a constant in the left side: log(f(n)) ≥ log(C1g(n)) ≥ log⁡(C1) + log⁡(g(n)) ≥ log⁡(g(n)) let's say C3log(g(n) < log(C1) C3 < log(C1)/log(g(n)) - is there a solution?

meaning i couldn't prove that log(f(n)) = Ω(log(g(n))). please, if you can, show me the complete proof.

big-o complexity-theory algorithm
2 Answers

By definition:

c1*g(n) <= f(n) <= c2 g(n), for n > n0

as functions are positive and log is an increasing function, we can have the following:

log(c1*g(n)) <= log(f(n)) <= log(c2*g(n)), for n > n0
=> log(c1) + log(g(n)) <= log(f(n)) <= log(c2) + log(g(n)), for n > n0

Now, as log(c1) + log(g(n)) <= log(f(n)), if c1 >= 1, we can conclude that:

log(g(n)) <= log(f(n))

Hence the proof is complete (similarly for log(f(n)) <= c2 * c1* log(g(n)) if c2 >= 1).

If c1 < 1 (so, log(c1) < 0), we need to find a constant c3 > 0 like the following:

c3 * log(g(n)) < log(c1) + log(g(n))

So,

 -log(c1) < (1-c3) log(g(n)) 
=> -log(c1)/(1-c3) <  log(g(n))

Now, as g(n) >= 2 for every n, if we have the following:

-log(c1)/(1-c3) < log(2) = 1

we will satisfy the definition of Omega. So, the following value for c3 is valid for the definition:

-log(c1)/(1-c3) < 1
=> -log(c1) < 1- c3 => c3 < 1 + log(c1)

Also, if log(c1) < -1, we need to find a m0, such that g(n) > k for every n > m0 and -log(c1)/(1-c3) < k has at leat one valid solution, i.e., c3 < 1 + log(c1)/k. In other words, we need to find m0 and k > 0 such that g(n) > k and log(c1)/k > -1. The former means the following:

log(c1) > -k => c1 > 2^(-k)
user_37688710

The statement is indeed true. To begin with, we suppose f(n) and g(n) are both increasing functions that go to infinity as n grows large. Then by definition of bit theta, there exists constants a and b such that

a*g(n)<=f(n)<=b*g(n)

Taking logarithms on both side we have

-log a+log g(n)<=log f(n)<=log g(n)+log b

Without loss of generality let's assume a<1 and b>1 and n is large enough such that g(n)>1. As a result, we obtain the following inequality:

log g(n)<=log f(n)<=(1+log b)log g(n)

This indicates that log f(n) is big theta of log g(n).

user_85939040
Related