1

I have showed that $f(n)=\Omega(g(n))$ in the following way.

We assume that $${\log n}^{\log n} \leq n/\log n$$ $$\implies \log n \times \log \log n \leq \log n - \log \log n$$ $$\implies \log \log n \times ( \log n -1 ) \leq \log n $$ which is a contradiction when $n \geq 1$. Thus we conclude $f(n) = \Omega(g(n))$ where we consider $c=1$ and $n_0 = 1$.

I will be thankful if anyone can comment that if my approach is correct or if incorrect may please provide the solution approach.

aghost
  • 559
  • 1
    $O$, $\Omega$, and the like regard the behaviors of the functions as $n \rightarrow \infty$. So to prove that $f \in \Omega(g)$ you should show that $\lim_{n\rightarrow\infty} cf - g \ge 0$ for some $c$. In this case you have $\lim_{n \rightarrow \infty} f-g = \infty$ by roughly the argument you made. – Reinstate Monica Jan 13 '15 at 16:01
  • Thank you. So any help please on showing the limit is greater than 0. Seems to be quite complicated.

    Or would you propose any other easier way to solve it?

     – aghost Jan 13 '15 at 16:10
  • 1
    Also $$(\log n)^{\log n} = (e^{\log\log n})^{\log n} = e^{\log n \cdot \log\log n} = (e^{\log n})^{\log\log n} = n^{\log\log n}.$$ – dtldarek Jan 13 '15 at 16:12
  • You basically did it. Using your method, show that $(\log n)^{\log n} - \frac{n}{\log n} = (\log\log n)(\log n) - \log n - \log\log n$. Then state that $\lim_{n \rightarrow \infty}$ of this expression is $\infty$. Then you are done. – Reinstate Monica Jan 13 '15 at 16:13
  • @ Solomonoff's Secret I think it will be equivalent to instead of equal to. Is not it? – aghost Jan 13 '15 at 16:23

0 Answers0