Is this function in the complexity?

Question

I am not sure about the following question:

Is log_a(n^b) in O(log_b(n^a)) for constants a, b?

Answer 1

When asked if a function f(x) is in O(g(x)) it really compares the rate of growth of those two functions. (see wikipedia: http://en.wikipedia.org/wiki/Big_O_notation)

Constant factors of the functions are ignored so 2x is in O(x). Also components of the function that have lower growth rates are similarly ignored so 2x^2 + x + 1 is in O(x^2).

So the question is: does loga n^b have a similar growth rate as logb n^a?

To solve this we will apply a couple of awesome properties of logarithms:

• log x^b = b log x
• loga x = (logb x) / (logb a)

First thing to do is to fix the big O notation we are comparing to as it is not minimal, by applying the first property above we get: O(logb n^a) = O(a logb n) because constant coeficient are removed from big O notations the real representation of the rate of growth is: O(logb n).

Now applying the first identity to the first formula we have:

loga n^b = b loga n

next we change the base using the second property we get:

loga n^b = b (logb n) / (logb a)

this can also be organized to look like:

loga n^b = (b / logb a) logb n

note that (b / logb a) is a constant coeficient therefore (b / logb a) logb n is in O(logb n)

So the answer to the question is yes. loga n^b is in O(logb n^a).

Answer 2

Let us write the first expression as b*log_a(n) and the second as a*log_b(n).

The first one is equivalent to b*log(n)/log(a) and the second one is a*log(n)/log(b).

So, the hypothesis is: "Are there an integers n₀ and k such that for all n>n₀, b*log(n)/log(a) < k*a*log(n)/logb ?"

With a bit of simplification, that would be: "... b/log(a) < k*a/log(b) ?"

With further rearrangements, we have: "... b*log(b) < k*a*log(a) ?"

Hence, the answer depends on what "a" and "b" are. It is a "yes" if b <= a.