Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
For those interested in relatively unknown logarithm identities, see and my short note Harmonious logarithm identities, Mathematical Gazette 93 #526 (March 2009), 95-97. – Dave L. Renfro Nov 15 '11 at 15:54
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|cite|improve this answer

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


share|cite|improve this answer

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|cite|improve this answer

Your Answer


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.