2
$\begingroup$

I was doing a time complexity problem, and the solution mentioned that there is a single class for logs. Ie. we can write $\log_a (x) = \Theta(\log_b(x))$ where $a$ is not equal to $b$.

This can be done because apparently logs are all multiples of each other:
$\log_a (x) = \log_b (x) \cdot \log_a (b)$

So we will always achieve:

$\lim_{x\to \infty} \frac{\log_a (x)}{\log_b(x)} = \text{some constant}$; where $0 < \text{some constant} < \infty$, thus we can use $\Theta$.

My question is how is it clear that $\log$s are all multiples of each other? How does $\log_a (x) = \log_b (x) \cdot \log_a (b)$ demonstrate this?

  • 1
    To add to David Mitra's derivation of $\log_a x = \log_b x \cdot \log_a b$, the reason why this demonstrates that $\log_a x = \Theta(\log_b x)$ is because $\log_a b$ is constant in $x$. So we could say that for any $a,b > 1$ there is a nonzero constant $k$ such that $\log_a x = k\log_b x$. It follows immediately that $\log_a x = \Theta(\log_b x)$. Then we have that for any $a,b>1$ and $x>0$ that $\frac{\log_a x}{\log_b x} = k$: you don't even need to take the limit for the ratio to be constant!2012-01-18
  • 3
    $\log_ab$ is a constant2012-01-18

1 Answers 1

1

For any positive $a$, $b$ and $x$ you have

$$\log_b(x) = \frac{\log_a(x)}{\log_a(b)}$$

so you can define the logarithm to any base $b$ once you've defined it for a single base $a$.

Pick your favourite base (many people like $a=10$, but computer scientists tend to prefer $a=2$ and mathematicians prefer $a=e$) and then the logarithm to base $b$ is the logarithm to base $a$, multiplied by $1/\log_a(b)$.

  • 2
    To summarize, the OP asks how to prove assertion (A) and your answer is: *You have (A)*. Hmmm...2012-01-18
  • 2
    The OP asked "How does $\log_a(x)=\log_b(x)\log_a(b)$ demonstrate that all logs are multiples of each other?" not "How do you prove that $\log_a(x)=\log_b(x)\log_a(b)$?"2012-01-18
  • 0
    Thanks, I guess I had forgotten that property of logarithms!2012-01-19