0
$\begingroup$

Consider binary logarithm . How is the value of ${(\frac 12 )}^{{\lg n}}$ = ${\frac 1n}$?

I was going through this video of skiplists and the professor at 53:22 seconds make this claim .

  • 0
    @BabakSorouh lg is log to the base 2.(binary logarithm)2012-08-30

2 Answers 2

4

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

Note that $2^{\lg n} = n$ because $2^{\lg n} = \left(e^{\log 2}\right)^{\lg n} = \left(e^{\log 2}\right)^{\log(n)/\log(2)} = e^{\log n} = n$.

Also, a lot of people write $\log_2 n$ instead of $\lg n$.

  • 0
    @AndréNicolas that is really more intuitive than this formal prrof. thanks for the hint.2012-08-30
1

$\forall\,0

I think your equality is missing the $\,\log 1/2\,$ as power...

Added: But we can write $n^{\log 1/2}=n^{-\log 2}=\frac{1}{n^{\log 2}}$

  • 0
    This must be a new symbol: never saw it before.2012-08-30