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.

  • $\begingroup$ 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 $\endgroup$ – 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. $$

  • $\begingroup$ Excellent, thank you, I'm a little dense when it comes to logarithms. I try to avoid them as much as possible! $\endgroup$ – TimeBomb006 Feb 29 '12 at 17:16

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

  • $\begingroup$ 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! $\endgroup$ – TimeBomb006 Feb 29 '12 at 17:04
  • $\begingroup$ @TimeBomb006, not really, it skips from 1 to 3 without using 2. $\endgroup$ – Peter Taylor Feb 29 '12 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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