Finding asymptotic relationship between: $\frac {\log n}{\log\log n} \overset{?} = (\log (n-\log n))$

Question

Given $f(n)=\frac {\log n}{\log\log n} , g(n)= (\log (n-\log n))$, what is the relationship between them $f(n)=K (g(n))$ where "K" could be $\Omega,\Theta,O$

I thought of taking a log to both sides and see what we get:

$\log\frac {\log n}{\log(\log n)}= \log(\log n) -\log[\log(\log n)] \overset{?} = c\log(\log (n-\log n))$

It looks like the RHS is smaller than: $\log(\log (n-\log n)) \le \log(\log n)$

And since $\log[\log(\log n)] < \log(\log n)$ then $\log(\log (n-\log n)) \le \log(\log n) - \log[\log(\log n)] $

But it's actually $O$, and I can't find a way to show it...

Answer 1

Look at $g(n)$: $$ g(n) = \log(n-\log n) = \log n + \log\left(1-\frac{\log n}{n}\right) = \log n + o(1) $$ using the fact that $\frac{\log n}{n} \xrightarrow[n\to\infty]{}0$ and $\frac{\ln(1+x)}{x} \xrightarrow[x\to 0]{}1$.

So $g(n) = \Theta(\log n)$. But $f(n) = \frac{\log n}{\log\log n} = o(\log n)$.

Answer 2

Hint:

$$\lim\limits_{n\to \infty}\frac{f(n)}{g(n)}= \lim\limits_{n\to \infty}\frac{\log n\bigg/\log(\log n)}{\log(n-\log n)}=\lim\limits_{n\to \infty}\frac{\log n}{\log(\log n)\log(n-\log n)}= \lim\limits_{n\to \infty}\frac{\log n}{\bigg(\log n+\log(1-\frac{\log n}{n})\bigg)\log(\log n)} =\lim\limits_{n\to \infty}\frac{\log n}{\log(\log n)\log n}= \lim\limits_{n\to \infty}\frac{1}{\log(\log n)}=0$$