0

I am trying to do the exercise 01, chapter 02 of the book: Algorithm Design [Kleinberg _ Tardos] - publication version 03 of the book

I need to manipulate $2^{\sqrt{\log_2n}}$, what I did was:

  1. $2^{\sqrt{\log_2n}}$
  2. $2^{\frac{1}{2}\log_2n}\impliedby$ Log property where $\log_b(n^a)=a\log_bn$
  3. $n^{\frac{1}{2}\log_22}\impliedby$ Log property where $a^{\log_bc}=c^{\log_ba}$
  4. $n^{\frac{1}{2}}\impliedby\log_22=1$

I don't know the correct answer. Moreover I know that the correct answer is smaller than $n^\frac{1}{3}$, and $n^\frac{1}{2}$is not smaller than $n^\frac{1}{3}$, so I messed up somewhere but I cannot find.

Catarina Nogueira
  • 127

1 Answers1

1

An expression like $2^{\sqrt{\log_2 n}}$ does not simplify to anything nicer.

First, the problem with the attempt in the question is that there is no rule to simplify $(\log x)^k$. We can simplify $\log(x^k)$ to $k \log x$, but there's nothing to be done when we first take the logarithm and then raise the result to a power. In particular, $\sqrt{\log_2 n} \ne \frac12 \log_2 n$. (To make this more obvious, let $y = \log_2 n$; then you are trying to simplify $\sqrt{y}$ to $\frac12 y$.)

We can make some comparisons between $2^{\sqrt{\log_2 n}}$ and other functions in terms of growth rates. More precisely:

  • For all $k>0$, no matter how large, $2^{\sqrt{\log_2 n}}$ grows more slowly than $n^{1/k}$: for large enough $n$ (depending on $k$), we have $2^{\sqrt{\log_2 n}} < n^{1/k}$. To see this, take the logarithm of both sides: we get $\sqrt{\log_2 n}$ on one side and $\frac1k \log_2 n$ on the other. In terms of $y = \log_2 n$ again, $\sqrt y$ will be less than $y/k$ provided $y > k^2$; therefore $2^{\sqrt{\log_2 n}} < n^{1/k}$ provided $n > 2^{k^2}$.
  • For all $k>0$, no matter how large, $2^{\sqrt{\log_2 n}}$ grows more quickly than $(\log_2 n)^k$. To see this, once again, take the logarithm of both sides: now we are comparing $\sqrt{\log_2 n}$ to $k \log_2 \log_2 n$, or in terms of $y = \log_2 n$, we are comparing $\sqrt{y}$ to $k \log_2 y$.
Misha Lavrov
  • 142,276
  • Oh, I see! Based on your answer, to try to visualise better, I'm trying to multiply by ${\log_2n}$ on both sides, so ${\log_2n}$x = ${\log_2n}$ $2^{\sqrt{\log_2n}}$. I arrived on ${\log_2n}$x = ${\log_2n}$${\sqrt{n}}$, which is basically the same I found before, there is still an error somewhere. I did now the following: 1) ${\log_2n}$* $2^{\sqrt{\log_2n}}$ . Then 2) ${\log_2n}$* ${\sqrt{2^\log_2n}}$ . Then 3) ${\log_2n}$* ${\sqrt{n^\log_22}}$ . Then 4) ${\log_2n}$*${\sqrt{n}}$ – Catarina Nogueira Mar 29 '24 at 22:18
  • 1
    Replacing $2^{\sqrt y}$ by $\sqrt{2^y}$ is also incorrect! – Misha Lavrov Mar 29 '24 at 22:22
  • So how can ${\log_2n}$* $2^{\sqrt{\log_2n}}$ be (log_2n)^1/2 ? I put on Wolfram Alpha and I got the answer like this, but I just cannot arrive there :( – Catarina Nogueira Mar 29 '24 at 22:25
  • "does not simplify to anything nicer", this sounds too categorical, especially since nicer is a subjective word. How can we prove it? Perhaps someone will find something "nicer" in some sense. – zkutch Mar 29 '24 at 22:29
  • 1
    Those two expressions are not equal, and my best guess is that you typed something into Wolfram Alpha that didn't mean what you thought it meant. Here is my attempt at entering it into Wolfram Alpha, and it doesn't simplify. – Misha Lavrov Mar 29 '24 at 22:30
  • @CatarinaNogueira Can you edit your question to include your new attempt and the WolframAlpha link? – peterwhy Mar 29 '24 at 22:32
  • 1
    @zkutch Though "nicer" is somewhat subjective, I think that the categorical statement is the best advice for someone who struggles working with this expression. Someone that can put into a different situationally more useful form in a special circumstance does not need my answer. – Misha Lavrov Mar 29 '24 at 22:32