0
$\begingroup$

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.

  • 0
    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**2012-03-01

2 Answers 2

1

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

  • 0
    Excellent, thank you, I'm a little dense when it comes to logarithms. I try to avoid them as much as possible!2012-02-29
0

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

  • 0
    @TimeBomb006, not really, it skips from 1 to 3 without using 2.2012-02-29