# How do you solve this simple logarithm problem?

I'm comparing efficiencies for the famous fake-coin algorithms. Specifically, I'm looking at a two-pile approach and a three-pile approach for a solution. I have found that, like a binary search, the two-pile approach efficiency grows at the rate of $\log$(base $2$)$n$, while the three-pile approach efficiency grows at the rate of $\log$(base $3$)$n$.

So I want to compare the rates at which they grow for large values of $n$; I made a ratio of two-pile to three-pile growth as follows:

$$\dfrac{\log_2 n}{\log_3 n}$$

I want my answer to NOT depend on $n$. I actually know the answer, but I want to know what logarithmic rules, arithmetic, etc., are used to find the answer.

Here is the answer, step by step:

STEP 1. $\dfrac{\log_2 n}{\log_3 n}$

STEP 2. = $\dfrac{\log_2 n}{\log_3 2 \log_2 n}$

STEP 3. = $\log_2 3$

STEP 4. approximately $= 1.6$

Edit: I forgot to add that I set up a recurrence relation, prior to steps 1-4, that sets $n = 3^k$, so I don't know if that effects the answer, I don't think it does.

-
Note that $\log$ that gives $\log$ looks better than $log$. Further, using $\dfrac{}{}$ gives your fractions a better look. But, overall, a well posed question. +1 – user21436 Mar 1 '12 at 2:22

The general logarithmic rule you want is the following: $\log_{a}{b} = \ln{b} / \ln{a}$. From this you can demonstrate each step in your derivation: $$\frac{\log_{2}n}{\log_{3}{n}} = \frac{\ln{n}/\ln{2}}{\ln{n}/\ln{3}} = \frac{\ln{3}}{\ln{2}}=\log_{2}{3} \approx1.585.$$
You can do this just using $\log_a b^c = c \; \log_a b$ and $x = \log_y z \iff y^x = z$ (ignoring the complex extension of the logarithm).
Let $k = \frac{\log_2 n}{\log_3 n}$. Then $\log_2 n = k \; \log_3 n = \log_3 n^k$. So $3^{\log_2 n} = n^k$ and we can take logs base 2 to get $\log_2 n \; log_2 3 = k \; \log_2 n$.
I'm sorry for my logarithmic ignorance, I still don't quite understand. After some research, I discovered that the base switch rule, or $log_b c = \frac{1}{\log_c b}$, applies to STEP 3. I was unaware of that rule. I still am trying to make sense of STEP 2 though. Does the set of equations you describe define the transformation that occurs from STEP 1 to STEP 2? As I mentioned, the goal is to eliminate n from the equation. I am going to revisit my initial post and reformat it. Thank you for your help! – TimeBomb006 Feb 29 '12 at 17:04