Big Oh-Complexity of $\log(\frac{n}{\log(n)})$ vs $\frac{\sqrt{n}}{\log(\sqrt{n})}$ Could you help me see which of the two functions
$f(n) = \log(\frac{n}{\log(n)})$ and $g(n) = \frac{\sqrt{n}}{\log(\sqrt{n})}$
grows asymptotically faster? I would say that $f(n) = \mathcal{O}(g(n))$, since $f(n)$ is logarithmic, but I am struggling to prove that formally. Could you help me with that? 
 A: If you are not interested in the asymptotic expansion per se you could just take the quotient and use L'Hôpital's rule:
$$\lim_{x\to\infty}\frac{f(x)}{g(x)}=\lim_{x\to\infty}\frac{f'(x)}{g'(x)}=\lim_{x\to\infty}\frac{\frac{1}{x}-\frac{1}{x\log x}}{\frac{1}{\sqrt x\log x}-\frac{2}{\sqrt x\log^2 x}}=\lim_{x\to\infty}\frac{1-\frac{1}{\log x}}{\frac{\sqrt x}{\log x}-\frac{2\sqrt x}{\log^2 x}}=0.$$
Thus, $g$ grows faster.
A: 
We obtain
  \begin{align*}
\color{blue}{f(n)}&=\log\left(\frac{n}{\log n}\right)\\
&=\log n-\log\log n\\
&=\log n+O(\log n)\\
&=O(\log n)\\
&=O\left(\frac{\sqrt{n}}{\log n}\right)\tag{$(\log n)^2=O(\sqrt{n})$}\\
&=O\left(\frac{\sqrt{n}}{\frac{1}{2}\log n}\right)\\
&\,\,\color{blue}{=O(g(n))}
\end{align*}
in accordance with OP's assumption.

A: Informally, log's don't count for much, so $f(n)\approx \log(n)$ and $g(n)\approx \sqrt{n}$, so $f(n)/g(n)\rightarrow 0$.  
Formally, for $n\geq3$
$$
\frac{f(n)}{g(n)} = \frac{\log\left(\frac{n}{\log{n}}\right)}{\frac{\sqrt{n}}{\log(\sqrt{n})}}
$$
$$
< \frac{\log(n)}{\frac{\sqrt{n}}{\log(\sqrt{n})}}= \frac{\log(n) \log(\sqrt{n})}{\sqrt{n}}
$$
$$
 = \frac12 \frac{\log(n)^2 }{\sqrt{n}}.
$$
Now using L'Hôpital's rule twice, 
$$
\lim_{n\rightarrow\infty} \frac{f(n)}{g(n)}\leq \lim_{n\rightarrow\infty}\frac{\log(n)^2 }{\sqrt{n}}
= \lim_{n\rightarrow\infty} \frac{2 \log(n)/n}{1/(\,2\sqrt{n}\,)}
$$
$$
= \lim_{n\rightarrow\infty} \frac{4 \log(n)}{\sqrt{n}}
= \lim_{n\rightarrow\infty} \frac{4/n}{1/(\,2\sqrt{n}\,)}
= \lim_{n\rightarrow\infty} \frac{8}{\sqrt{n}}=0.
$$
