Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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! –  Clive Newstead Jan 18 '12 at 13:52
3  
$\log_ab$ is a constant –  yoyo Jan 18 '12 at 14:48

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
2  
To summarize, the OP asks how to prove assertion (A) and your answer is: You have (A). Hmmm... –  Did Jan 18 '12 at 13:27
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)$?" –  Chris Taylor Jan 18 '12 at 14:30
    
Thanks, I guess I had forgotten that property of logarithms! –  rrazd Jan 19 '12 at 1:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.