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?

  • 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)$.

  • 0
    Thanks, I guess I had forgotten that property of logarithms!2012-01-19