7
$\begingroup$

Is $n^{1/\log \log n} = O(1)$ ?

Suppose that $n^{1/\log \log n} = c$ where $c$ is constant.

Taking logs of both sides,

$$\frac{1}{\log \log n}\log n = \log c.$$

I am not able to spot an error. Please help

$\endgroup$
  • 1
    $\begingroup$ Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Nov 26 '19 at 20:22
7
$\begingroup$

The function $n^{1/\log \log n}$ tends to infinity, since $$ n^{1/\log\log n} = e^{\log n/\log\log n}, $$ and $\log n/\log \log n \longrightarrow \infty$.

$\endgroup$
2
$\begingroup$

In your last step, a contradiction is reached since (by L'Hopital) $$\lim_{n\to\infty}\frac{\log n}{\log\log n}=\lim_{n\to\infty}\frac{1/n}{1/(n\log n)}=\lim_{n\to\infty}\log n$$ and $\log$ is unbounded.

$\endgroup$
1
$\begingroup$

There isn't an error. You supposed that $n^{1/\log\log n}$ is constant and you derived the contradiction that $\log n/\log\log n$ is constant. Therefore, your supposition must be false.

It would have been better to have written that $n^{1/\log\log n}\leq c$ for all $n$, since you're really trying to show that the function is bounded above by a constant, not that is constant.

$\endgroup$
0
$\begingroup$

We can calculate this by applying Taylor series and L'Hôpital's rule accordingly:

$$\lim_{n\to\infty}n^{\frac{1}{\log\log{n}}}\geq\lim_{n\to\infty}n^{\frac{1}{\ln\ln{n}}}=\left [ k=\ln{n}, n=e^{k} \right ]=\lim_{k\to\infty}(e^{k})^{\frac{1}{\ln{k}}}=\lim_{k\to\infty}e^{\frac{k}{\ln{k}}}=\left [ t = \frac{k}{\ln{k}} \right ]=\lim_{t\to\infty}e^{t}\geq\lim_{t\to\infty}(1 + t)=1 + \lim_{t\to\infty}t=\infty$$

As you can see it tends to infinity.

$\endgroup$
0
$\begingroup$

By way of contradiction, suppose $n^{1/ \log \log n} = O(1)$. Then, by definition of the big-O notation, there exist positive constants $c$ and $n_0$ such that $n^{1/\log \log n} \le c$ for all $n \ge n_0$. Taking log of both sides, we obtain that $\frac{\log n}{ \log \log n}$ is at most some constant $c' = \log c$ for all sufficiently large $n$. But this is impossible because it can be shown (for eg by L'Hopital's rule) that $\lim_{n \rightarrow \infty} \frac{\log n}{\log \log n} = \infty$.

$\endgroup$

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.