5
$\begingroup$

I found this problem in some notes linked on the course page of a particular online class that I am taking. I am not sure if I am allowed to provide them here, so hopefully context does not matter too much. In this post, I use the phrase $f(x)\asymp g(x)$ to mean that $$\lim_{x\to\infty}\frac{f(x)}{g(x)}=M\in\Bbb R \setminus \{0\},$$ i.e. $f$ and $g$ have the same growth rate.


Determine if $\ln^{\ln(x)}(x)\in O(x^2)$.

My Attempt: I believe the answer is yes. The simplest way to prove such a claim, as far as I am aware, is to apply L'Hôpital's rule to the limit $\lim_{x\to\infty}\ln^{\ln(x)}(x)/x^2$. But, first of all, let $f=\ln^{\ln(x)}(x)$. Then, by rules of logarithms it is clear that $\ln(f)=\ln(x)\cdot\ln(\ln(x))$, and moreover $$\require{cancel}\begin{align}f'\cdot\frac{1}{f} &= \frac{d}{dx}[\ln(x)\cdot\ln(\ln(x))] \\ &=\frac{1}{x}\cdot\ln(\ln(x))+\cancel{\ln(x)}\cdot\frac{1}{\cancel{\ln(x)}}\cdot\frac{1}{x} \\ &=\frac{\ln(\ln(x))+1}{x}\end{align}.$$ Thus, $$f'=\frac{\ln^{\ln(x)}(x)(\ln(\ln(x))+1)}{x}.$$ From here, an application of L'Hôpital's rule yields $$\begin{align}\lim_{x\to\infty}\frac{\ln^{\ln(x)}(x)}{x^2} &=\lim_{x\to\infty}\frac{\ln^{\ln(x)}(x)(\ln(\ln(x))+1)}{x^2} \\ &=\lim_{x\to\infty}\ln^{\ln(x)}(x) \ \cdot \ \underbrace{\lim_{x\to\infty}\frac{\ln(\ln(x))+1}{x^2}}_{(\star)},\end{align}$$ and it suffices to prove that the limit $(\star)$ is zero; namely that $O(x^2)\ni \ln(\ln(x))+1\asymp\ln(\ln(x))$. Accordingly, we have $$\require{cancel}\lim_{x\to\infty}\frac{\ln(\ln(x))}{\ln(x)}=\lim_{x\to\infty}\frac{\cancel{x}}{\cancel{x}\ln(x)}=0.$$ which implies that $\ln(\ln(x))\in O(\ln(x))$ (as one could pick $M=1$ and some sufficiently large value of $x_0$ in the definition). But, since $$\lim_{x\to\infty}\frac{\ln(x)}{x^2}=\lim_{x\to\infty}\frac{1}{x^2}=0,$$ we have that $$O(\ln(x))\subsetneq O(x^2)\implies\ln(\ln(x))\in O(x^2).$$ Therefore, the limit $(\star)$ is zero and $\ln^{\ln(x)}\in O(x^2)$.


Is this proof correct? Can it be improved upon? Usually, to prove something like this given two functions $f$ and $g$, one would choose a value $x_0$ and then construct a constant $M$ so that $|f(x)|\le Mg(x)$, but in this case, I was not sure how to do that. Also, if you prefer, the notation $f(x)\in O(g(x))$ could be swapped with $f(x)=O(g(x))$.

Thanks in advance!

Edit: Now that I realize my claim is false, is it possible to prove that $x^2\in O(\ln^{\ln(x)}(x))$?

$\endgroup$
11
  • $\begingroup$ Are you sure that $(\ln x)^{\ln x} \in O(x^2)$? $\endgroup$
    – Fabian
    Jun 23, 2018 at 12:51
  • 2
    $\begingroup$ Note that $(\ln x)^{\ln x} = x^{\ln \ln x}$. What can you say for $x\to \infty$. $\endgroup$
    – Fabian
    Jun 23, 2018 at 12:52
  • 2
    $\begingroup$ @Crosby: that is an illusion. Try to compare them at $x\approx 10^4$ $\endgroup$
    – Fabian
    Jun 23, 2018 at 12:54
  • 2
    $\begingroup$ Your proof falls apart when you introduce the *, can you see why? $\endgroup$ Jun 23, 2018 at 12:56
  • 2
    $\begingroup$ @cansomeonehelpmeout Oh, I see. Both limits have to be finite. $\endgroup$
    – Crosby
    Jun 23, 2018 at 13:17

1 Answer 1

6
$\begingroup$

As the comments suggest, the entire claim fails.

To orient yourself, use the "commutative" law for exponentiation:

$u^{\ln (v)}=\exp(\ln (u) \ln (v))=\exp(\ln (v) \ln (u))=v^{\ln (u)}$

Here $u=\ln (x), v=x$ and you have

$(\ln (x))^{\ln (x)}=x^{\ln(\ln (x))}$

The exponent on $x$ goes only slowly to infinity, but it does go to infinity as $x$ itself does so. So $(\ln (x))^{\ln (x)} \notin O(x^n)$ for any finite $n$.

$\endgroup$
3
  • $\begingroup$ Okay, thank you. Is it possible to prove that $x^2\in O(\ln^{\ln(x)}(x))$, then? $\endgroup$
    – Crosby
    Jun 23, 2018 at 13:22
  • $\begingroup$ That works, for $x^n$ given any finite $n$ in place of $x^2$. $\endgroup$ Jun 23, 2018 at 13:25
  • 1
    $\begingroup$ (+1) Okay, got it. Thanks for you answer! $\endgroup$
    – Crosby
    Jun 23, 2018 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.