1
$\begingroup$

I'm trying to understand the asymptotic growth of relationship between log(log(n)) and log(n) / log(log(n)) as n -> infinity. Specifically, I want to verify whether this statement is true or false: log(log(n)) = O(log(n) / log(log(n)))

Could someone help confirm whether this is true or false?

Thank you for your insights!

I was initially confused because (log(log(n)))^2 appears to grow faster than log(n) for large n, but I suspect my intuition may be wrong.

New contributor
maybesunny is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
1
  • $\begingroup$ Yes it is true. But when we say grow faster this is really an asymptotic statement. For fixed and reasonably sized values of $n$ a slower growing function may still be larger than a faster growing. Take 10^100 and O(n) as examples. The former doesn't grow at all. $\endgroup$
    – Simd
    Commented Dec 9 at 19:21

1 Answer 1

Reset to default
2
$\begingroup$

Let $k=\log n$, so we are considering $\log k$ and $k/\log k$. We just need to calculate a simple limitation $$\lim_{k\rightarrow\infty}\frac{\log k}{k/\log k}.$$ If the limitation is $0$ then $\log k=o(k/\log k)$. Thus $\log\log n=O(\log n/\log\log n)$.

$$\lim_{k\rightarrow\infty}\frac{\log k}{k/\log k}=\lim_{k\rightarrow\infty}\frac{\log^2 k}{k}=\lim_{k\rightarrow\infty}\frac{2\log k}{k}=0.$$

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Can you explain the step $\lim_{k\rightarrow\infty}\frac{\log^2 k}{k}=\lim_{k\rightarrow\infty}\frac{2\log k}{k}$? $\endgroup$
    – Kelly Bundy
    Commented Dec 9 at 20:09
  • 1
    $\begingroup$ @KellyBundy I am assuming that the base of $\log$ is $e$. L'hospital method is applied to infer the step. $\endgroup$
    – minh quý lê
    Commented Dec 9 at 21:27
  • 2
    $\begingroup$ @KellyBundy the derivative of $\log^2 k$ is $2 \log k / k$. $\endgroup$
    – John Kemeny
    Commented Dec 9 at 22:36
  • $\begingroup$ @JohnKemeny yes but the derivative of $k$ is $1$, so the ratio of the derivatives is $\frac{(2\log k) / k}{1} = \frac{2\log k}{k}$ $\endgroup$
    – SilvioM
    Commented Dec 10 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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