# How is O(log(log(n))) also O(logn)? 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.

How is $O\left(\mathrm{log}\left(\mathrm{log}\left(n\right)\right)\right)$ also $O\left(\mathrm{log}n\right)$?
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.
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

getrdone07tl
Suppose $f\left(n\right)=O\left(\mathrm{log}\mathrm{log}n\right)$, and we want to prove that $f\left(n\right)=O\left(\mathrm{log}n\right)$
Assume $f\left(n\right)$ is a positive function. By the definition of the big $O$ notation, $f\left(n\right)=O\left(\mathrm{log}\mathrm{log}n\right)$ implies that there exists a ${N}_{0}$ and a positive constant $k$ such that

Since $\mathrm{log}\mathrm{log}n\le \mathrm{log}n$ for sufficiently large $n$, there must exist a ${N}_{1}$ such that

thus $f\left(n\right)=O\left(\mathrm{log}n\right)$
###### Did you like this example?
mafalexpicsak
This is because, if $n$ is large enough, $|f|\le K\mathrm{log}\left(\mathrm{log}n\right)$ for some constant $K$ and $\mathrm{log}x\le x$ for all $x$
More generally, if $f=O\left(g\right)$ and $g=O\left(h\right)$ then $f=O\left(h\right)\phantom{\rule{thinmathspace}{0ex}}$$\phantom{\rule{thinmathspace}{0ex}}\left(O\left(O\left(h\right)\right)=O\left(h\right)$