Search code examples
algorithmasymptotic-complexity

If f(n) = O(g(n)), is log(f(n)) = O(log(g(n))?

I just learnt today that this relation does not hold, because log changes the behavior of the functions. But is it true? An example will be good.

And also if f(n) = ϴ(g(n)), will log(f(n)) = ϴ(log(g(n)) hold?

Any help is appreciated. Thanks in advance.

Solution

  • Now that comments have revealed that this question is about asymptotic limits rather than about algorithmic complexity .....

    You can use L'Hôpital's rule (information is in any basic text on differential calculus) and the fact that the derivative of ln(x) (natural logarithm) is 1/x to show that the asymptotic limit of f(n)/g(n) is equal to the asymptotic limit of log(f(n))/log(g(n)).

    Note that this has little or nothing to do with algorithmic complexity though.