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