2

I was reading the solution to 3.2-4 on this blog (cropped image pasted here)

enter image description here

notice the person says $\frac{(\lg n)^{\lg n}}{n} = \frac{n^{\lg \lg n}}{n}$

What log law justifies that?

Also, is it correct that it's an error to where they simplify $e^{\lg n}$ to $n$ in the denominator?

mring
  • 239

4 Answers4

5

It's a chain of log simplifications. I assume by $\lg$ the author means natural logarithm, by which $e^{\lg n} = n$ as a defining property (to answer your second question).

$$(\lg n)^{\lg n} = \left(e^{(\lg \lg n)}\right)^{\lg n} = e^{(\lg \lg n)(\lg n)}= e^{(\lg n)(\lg \lg n)} = (e^{\lg n})^{(\lg \lg n)} = n^{\lg \lg n}$$

Thomas Belulovich
  • 3,891
  • 1
    Actually, this is an algorithms problem from a computer science text and lg means log base 2, not base e (ln), which is why I think there's a problem there. – mring Jul 17 '13 at 16:56
  • 2
    $\lg$ usually means $\log_2$, but the proof is the same, with $e$ replaced by 2. – MJD Jul 17 '13 at 17:02
  • 1
    The log simplification is valid in any base, then (replace $e$ above with $2$), but then yes $e^{\lg n} = (2^{\lg e})^{\lg n} = n^{\lg e}$. – Thomas Belulovich Jul 17 '13 at 17:02
4

Start with $(\lg n)^{\lg n}$. Take its log: $$ \lg\left((\lg n)^{\lg n}\right)=\lg n\cdot\lg\lg n $$ by the power property of logs. Now do the same thing with $n^{\lg\lg n}$: $$ \lg\left(n^{\lg\lg n}\right)=\lg\lg n\cdot\lg n $$ The two are the same, so since the log function is one-to-one we have $$ (\lg n)^{\lg n}=n^{\lg\lg n} $$

Added. For your last question, yes, it was an error to say that $e^{\lg n}=n$. In fact, $$ e^{\lg n} = 2^{\lg(e^{\lg n})}=2^{\lg n\cdot\lg e}=n^{\lg e}\approx n^{1.44269} $$

Rick Decker
  • 8,718
1

If $y = (\ln n)^{\ln n}$ then $\ln y = (\ln n)(\ln (\ln n))$.

I used $\ln x^y \equiv y \ln x$ to get this.

If $\ln y = (\ln n)(\ln(\ln n))$ then $y = \operatorname{e}^{(\ln n)(\ln(\ln n))} \equiv (\operatorname{e}^{\ln n})^{\ln(\ln n)} \equiv n^{\ln(\ln n)}.$

I used $(x^a)^b \equiv x^{ab}$ and $\operatorname{e}^{\ln y} \equiv y$ to get this.

Fly by Night
  • 32,272
0

Expand each of them using $a^b = 2^{b \lg a}$.

The simplification you question is not an equality but an inequality.

dfeuer
  • 9,069