1

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.

Gary
  • 31,845
mik493
  • 13
  • 5
    It is $\log \log n -\log\log\log n$ as you showed. It follows from the general properties of logarithm as you showed. What is the question? – Gary Nov 27 '21 at 07:45
  • @Gary If that's true, my question is how did we reach $log : log : n$ using the approach that I described in my question. Where did it appear from? – mik493 Nov 27 '21 at 07:49
  • 1
    Seems your question may be related to algorithm complexity. In this case the question could be why this term is dominating. But there is no such context on your question. There is an omega function coming from nowhere without definition. – jlandercy Nov 27 '21 at 07:53
  • @jlandercy It is related to this subject, what I posted in my question is an excerpt from a larger series of calculations which are aimed to prove that if a Turing machine runs in $\Omega (log : log : n)$ space, it accepts a set that is not regular. Do you think it's possible that the result is $log : log : n - log : log : log : n$, but in this context we can dismiss the $log : log : log : n$ as a constant? – mik493 Nov 27 '21 at 07:59

1 Answers1

0

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)$.

Gary
  • 31,845
  • 1
    Thank you for your help, I understand your solution. I have marked your answer as accepted. – mik493 Nov 27 '21 at 09:44