6
$\begingroup$

How is $O(\log(\log(n)))$ also $O( \log n)$?

I have seen this result somewhere with this but I still didn't quite understand how this is true. This would also help me compute Big Omega of the same function.

$\endgroup$
  • $\begingroup$ What is probably meant is that each function that is $O(\log \log n)$ is also $O(\log n)$. But note that $\log n$ is in the latter but not the former (as $n \to \infty$). $\endgroup$ – D Poole Sep 7 '14 at 23:04
4
$\begingroup$

Suppose $f(n) = O(\log\log n)$, and we want to prove that $f(n) = O(\log n)$.

Assume $f(n)$ is a positive function. By the definition of the big $O$ notation, $f(n) = O(\log\log n)$ implies that there exists a $N_0$ and a positive constant $k$ such that $$ f(n) \leq k\cdot \log\log n, \ \forall n \geq N_0 $$

Since $\log\log n \leq \log n$ for sufficiently large $n$, there must exist a $N_1$ such that $$ f(n) \leq k \cdot \log n, \ \forall n \geq N_1 $$ thus $f(n) = O(\log n)$.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

This is because, if $n$ is large enough, $\lvert f\rvert\le K\log(\log n)$ for some constant $K$ and $\log x \le x$ for all $x$.

More generally, if $f=O(g)$ and $g=O(h)$ then $f=O(h)\,$ $\,(O(O(h))=O(h)$).

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Firstly, we assume all functions are nonnegative. $f(n)$ is $O(g(n))$ if $$\lim_{n\rightarrow \infty} \sup \frac{f(n)}{g(n)} \leq K<\infty\quad(1)$$ where the finite constant $K$ is independent of $n.$ Thus if $f(n)=O(g(n))$ and $h(n)\leq f(n)$ for $n$ large enough, then $h(n)=O(g(n)).$

If $K=0$ then we say $f(n)=o(g(n))$ but it still holds that $f(n)=O(g(n)).$

If $f(n)=O(g(n))$ and $g(n)=O(f(n))$ then $f(n)=\Theta(g(n))$ i.e., they are the same order up to a finite constant, for $n$ large enough.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why should $\dfrac{f(n)}{g(n)}$ have a limit? $\endgroup$ – Bernard May 30 '15 at 8:18
  • $\begingroup$ @Bernard, thanks for spotting the mistake. $\endgroup$ – kodlu May 30 '15 at 9:06

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.