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 am asking another question at StackOverflow about Big-O

On 1st line is something like

The size of the problem at level k is (2/3)kn. The size at the lowest level is 1, so setting (2/3)kn = 1, the depth is k = log1.5 n (divide both sides by (2/3)k, take logs base 1.5).

the main question is I have

$$1 = \left(\frac{2}{3}\right)^k \cdot n$$

I want to find k. I did

$$\left(\frac{2}{3}\right)^k n=1$$ $$\left(\frac{2}{3}\right)^k=\frac{1}{n}$$ $$k\lg\frac{2}{3}=\lg\frac{1}{n}$$ $$k=\frac{\lg\frac{1}{n}}{\lg\frac{2}{3}}$$ $$k=\lg_{\frac{2}{3}}\frac{1}{n}$$

I suppose I could somehow convert it to the desired answer $\lg_{1.5}{n}$?

share|improve this question
    
For those interested in relatively unknown logarithm identities, see mathforum.org/kb/message.jspa?messageID=6470549 and my short note Harmonious logarithm identities, Mathematical Gazette 93 #526 (March 2009), 95-97. –  Dave L. Renfro Nov 15 '11 at 15:54
add comment

3 Answers

up vote 1 down vote accepted

Your calculations are correct. In order to convert it to the desired answer, you need to use that $\log a/b = \log a - \log b $. Then, you can write

$$k = \frac{\log 1/n}{\log 2/3} = \frac{- \log n}{-\log 3/2} = \log_{1.5}n.$$

share|improve this answer
add comment

What they wanted you to do is

$$\left(\frac{2}{3}\right)^kn=1 \iff n=\left(\frac{3}{2}\right)^k$$

by dividing both sides by $\left(\frac{2}{3}\right)^k$. Then you can solve by hand again and get the desired result.

Alternatively you can use

$$\log_\frac{2}{3}(n^{-1})=-\log_\frac{2}{3}(n)=\log_\frac{3}{2}(n)$$

share|improve this answer
add comment

Yes, you could. What you need is

$$\log\frac1x=-\log x\;.$$

You can use that to swap the fractions in both logarithms, and the resulting signs will cancel. However, perhaps slightly easier would be to divide the equation by $(2/3)^k$ instead of $n$ in the first place; then you'd immediately get $(3/2)^k=n$ and thus $k\log(3/2)=\log n$.

share|improve this answer
add comment

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.