1
$\begingroup$

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}$?

  • 0
    For those interested in relatively unknown logarithm identities, see http://mathforum.org/kb/message.jspa?messageID=6470549 and my short note *Harmonious logarithm identities*, Mathematical Gazette 93 #526 (March 2009), 95-97.2011-11-15

3 Answers 3

1

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

2

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

1

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