What is $\log (\frac{\log n}{\log \log n})?$
The end result that I'm trying to reach is $\log \log n$. I'm not sure whether this is correct, because I found a rule that states that $\log (\frac{x}{y}) = \log x – \log y$, so according to this rule the result should be $\log (\frac{\log n}{\log \log n}) = \log \log n – \log \log \log n$, which is not equal to $\log \log n$.
To put things into perspective, at the beginning we have an equation $x(n) = \Omega \left( \frac{\log n}{\log \log n} \right)$. Then we apply the $f(n) = \Omega (g(n)) \Rightarrow f(n) \geq cg(n)$ theorem, but we take $\log$, so the theorem is $\log f(n) \geq \log g(n) + \log c$. After applying the theorem to our equation we are left with $\log x(n) \geq \log \log n – 1$. What I'm not sure about is where did we get the $\log \log n$ from. Is it somehow possible to take $\log$s with the $\Omega$ notation equation itself?
Thank you for any help in advance, I seem to be pretty confused about this.
Best Answer
Note that by the definition of $\Omega$, we have $$ x(n) \ge c\frac{{\log n}}{{\log \log n}} $$ for some $c>0$ and sufficiently large $n$. That is $$ x(n) \ge \sqrt{\log n} \frac{{c\sqrt {\log n} }}{{\log \log n}}. $$ Now $$\mathop {\lim }\limits_{n \to + \infty } \frac{{c\sqrt {\log n} }}{{\log \log n}} = + \infty , $$ so $$\frac{{c\sqrt {\log n} }}{{\log \log n}} > 1$$ for sufficiently large $n$. This implies that $$ x(n) \ge \sqrt {\log n} \Rightarrow \log x(n) \ge \frac{1}{2}\log \log n $$ for large $n$, meaning that $\log x(n) =\Omega(\log\log n)$.