0

I need to prove that $$\forall \epsilon >0 \quad log(log(n)) = O(log^\epsilon(n))$$.
I started by citing a known result which is (*) $$\forall \epsilon >0 \quad log(n) = O(n^\epsilon)$$
Then we can say that $\exists n_0, c$ such that $\forall n>n_0 \quad log(n) \leq c \cdot n^\epsilon$
Then continued with applying $log(n)$ function on the above inequality (since $log(n)$ is monotone the inequality remains)
$log(log(n)) \leq log(c) + log(n^\epsilon)$
Since $log(n)$ is unbound and approaches infinity we can say that $\exists k$ such that $log(c) + log(n^\epsilon) \leq k \cdot log(n^\epsilon)$

So to conclude we arrived at $log(log(n)) \leq k \cdot log(n^\epsilon)$

Not sure how to continue and if what I have done so far is on the right path.

EDIT: Is it valid to substitute $n$ with $log(t)$ and immediately prove this claim (using *)?

Eliran Turgeman
  • 183

1 Answers1

1

I think you can take a very direct approach starting from the following statement: We have $\log \log \log n = \mathcal{O}(\log \log n)$. Hence for fixed $\epsilon > 0$ we get $\log \log \log n \leq \epsilon \log \log n$ for $n$ large enough. Rewriting the RHS yields $\log ((\log n)^{\epsilon})$. Now apply $\exp$ on both sides to conclude:

$$\exp \log \log \log n \leq \exp \log ((\log n)^{\epsilon})$$

for $n$ large enough. As a last step, $\exp$ and $\log$ cancel on both sides.

sebastian
  • 2,130
  • After thinking a bit more I think that this solution is not accurate. In order for it to be accurate, we need to rely on the fact that $logloglogn=o(loglogn)$. (little o instead of big O), do you agree? – Eliran Turgeman Nov 08 '20 at 16:53
  • I don't think so (but maybe I'm overlooking something). We need to prove that for all $\epsilon > 0$ there exists $C$ and an $n_0 \in \mathbb{N}$ such that for all $n \geq n_0$ we have $\log \log n \leq C (\log n)^{\epsilon}$. I show that if we fix $\epsilon$ then such a $C$ and $n_0$ exist. Observe that from $\log \log \log n = \mathcal{O}(\log \log n)$ it follows $\log \log \log n = \mathcal{O}(\epsilon \log \log n)$ for fixed $\epsilon > 0$. – sebastian Nov 09 '20 at 10:08
  • I am still not sure but I think that the gap (in the solution or in my understanding) is where you say that you fix some $\epsilon$. This $\epsilon$ is derived from $logloglogn=O(loglogn)$ and from the definition of big O it suggests that exists such constant, not that it works for all constants (in comparison to little o) – Eliran Turgeman Nov 09 '20 at 10:15
  • 1
    Ah you are right. This might not be obvious. But notice that big-O still suffices, its just that the following argument is missing: Assume that $f = \mathcal{O}(g)$ for any suitable functions $f, g$. Then there exists $C$ such that for $n$ large enough we have $f(n) \leq Cg(n)$. Hence for fixed $\epsilon$ there exists $C'$ such that $f(n) \leq C' \epsilon g(n)$ (define $C' = \frac{C}{\epsilon}$). Hence $f = \mathcal{O}(\epsilon g(n))$. – sebastian Nov 09 '20 at 15:22