Prove that for all constants $a, b>1$, $\log_a{n}$ is $\Theta(\log_b{n})$

Question

So far I have established that I should be showing the following relationship:

$k_{1}$ $\leq\ \frac{\log_a{n}}{\log_b{n}} \leq\ k_{2}$ where $k_{1}, k_{2}$ $>$ 0

but I'm not sure how to go about this.

Any ideas?

Simply Beautiful Art · Accepted Answer · 2016-12-26T20:37:04.727

0

According to the change of base formula, we have

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

And then notice that

$$0<\log_a(b)<b$$

edited Dec 26 '16 at 20:37

answered Dec 26 '16 at 20:30

Is it not:
$$\frac{\log_a(n)}{\log_b(n)}=\log_b(a)$$
– user402081 Dec 26 '16 at 20:48
@user402081 No, that is not. Take $a=2,b=4$, for example. – Simply Beautiful Art Dec 26 '16 at 20:50
@user402081 No, I can assure you its right XD – Simply Beautiful Art Dec 26 '16 at 20:54
Sorry, I just started using Stack Exchange so I'm not getting the hang of refreshing comments just yet. I don't get how you got to that point? – user402081 Dec 26 '16 at 20:55
Is it just a rule that log base x y = (log base y x) ^-1? – user402081 Dec 26 '16 at 20:56
@user402081 See this graph – Simply Beautiful Art Dec 26 '16 at 20:56
@user402081 I used $\log_b(n)=\frac{\log_a(n)}{\log_a(b)}$, which is the change of base formula. – Simply Beautiful Art Dec 26 '16 at 20:57
How did you find the upper bound? – user402081 Dec 26 '16 at 21:01
@user402081 Logarithms obvious decrease the number inside it, right? – Simply Beautiful Art Dec 26 '16 at 21:02
Yeah but you would never even get remotely close to b no matter what numbers you put inside – user402081 Dec 26 '16 at 21:03
@user402081 And thus, it is an upper bound. QED? – Simply Beautiful Art Dec 26 '16 at 21:04

1 Answers1