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

share|improve this question
    
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

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
    
Excellent, thank you, I'm a little dense when it comes to logarithms. I try to avoid them as much as possible! –  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$.

share|improve this answer
    
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
    
@TimeBomb006, not really, it skips from 1 to 3 without using 2. –  Peter Taylor Feb 29 '12 at 19:04

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.