1

Let $c>0$ be a constant and $n$ go to infinity.

Asymptotically why is it the case that $\frac{c^{2(\log\log n)+1}-1}{c-1}\sim \log n^{2\log c}$ ?

I don't think it changes anything but the actual relation is $$\frac{2c\log\log n}{n}\frac{c^{2(\log\log n)+1}-1}{c-1}\sim\frac{2c\log\log n}{n}\log n^{2\log c}$$ as $n\rightarrow\infty$.

I don't see how this is true.

I've tried to transform the left value but I don't see how we $\log c$ can appear. And Why does $c<1$ versus $>1$ not matter?

Could the relation be true if we replace $\sim$ by $\lesssim$? (i.e. left =$O$(right))?

H. Walter
  • 979
  • 4
  • 9

2 Answers2

1

With asymptotics, constant multipliers are irrelevant. You can actually reduce the problem to $$c^{\log\log n}\sim (\log n)^{\log c}$$ which is just $$c^{\log N}\sim N^{\log c}$$ which I believe is an algebraic identity.

Edit: I left out that $$c^{2\log\log n}\sim (\log n)^{2\log c}$$ and $$c^{\log\log n}\sim (\log n)^{\log c}$$ are equivalent since $$\frac{c^{2\log\log n}}{(\log n)^{2\log c}}=\left( \frac{c^{\log\log n}}{(\log n)^{\log c}}\right)^{2} $$ So, if $$\frac{c^{2\log\log n}}{(\log n)^{2\log c}}\rightarrow \text{constant}$$ then $$\frac{c^{\log\log n}}{(\log n)^{\log c}}\rightarrow \text{constant}$$

user37344
  • 275
0

If $c>1$, \begin{align} \frac{2c\log\log n}{n}\frac{c^{2(\log\log n)+1}-1}{c-1} &= \frac{2c\log\log n}{n}\frac{c\cdot \left(\log n\right)^{2\log c}}{c-1} - \frac{2c\log\log n}{n}\frac{1}{c-1}\\ &= O\left(\frac{\log\log n\left(\log n\right)^{2\log c}}{n}\right) + O\left(\frac{\log\log n}n\right)\\ &= O\left(\frac{\log\log n\left(\log n\right)^{2\log c}}{n}\right). \end{align} If $c<1$, we get $O\left(\frac{\log\log n}n\right)$ at last.

Aforest
  • 2,665