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

  • 2
    Or $2^{\lg n}=n$ because $\lg n$ is defined to be the $x$ such that $2^x=n$.2012-08-30
  • 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
    Please see my edited question .2012-08-30
  • 0
    Watch out: $\lg(n)=\ln(n)/\ln(2)$.2012-08-30
  • 0
    This must be a new symbol: never saw it before.2012-08-30