Improving time complexity from O(log n/loglog n) to O((log ((nloglog n)/log n))/loglog ((nloglog n)/log n))
Here are the functions. 
$$f(n) = \frac{\log(n)}{\log\log(n)}$$ 
$$h(n)=\frac n{f(n)}=\frac{n\log\log(n)}{\log(n)}$$ 
$$g(n)=f(h(n))=\frac{\log(\frac{n\log\log(n)}{\log(n)})} {\log\log(\frac{n\log\log(n)}{\log(n)})}$$




  
  Is $g(n) &lt; f(n)$ in fact true (starting from some $n$)?
  


Yes, here is a proof.

Let us compute the derivative of $f(x)$ with respect to $x$ as a real variable.

$$\frac{df}{dx}
=\frac{\frac{\log\log x}{x}-\frac{\log x}{x\log x}}{(\log\log x)^2}
=\frac{\log\log x-1}{x\ (\log\log x)^2}$$

So $\frac{df}{dx}\gt0$ when $e^e &lt;x$. That means, $f(x)$ is strictly increasing once $e^e\lt x$. 

If $n$ is large enough, $e^e\lt h(n) \lt n$, which implies $f(h(n)) &lt; f(n)$, i.e., $g(n) &lt; f(n)$.

If we want to be specific, we can show that $e^e\lt h(n) \lt n$ when $n &gt; e^{e+2}$. 


  
  Is $g(n)$ asymptotically better the $f(n)$, i.e. is $g(n) = o(f(n))$?
  


No, $g(n) = \Theta(f(n))$. In fact, $\displaystyle\lim_{n\to\infty}\frac{g(n)}{f(n)}=1$


  
  Assuming this is asymptotically better, I can do ...
  


Well, that assumption is invalid.



Here are two exercises.

Exercise 1. Show that $\displaystyle\lim_{n\to\infty}\frac{g(n)}{f(n)}=1$ using the following hint or steps. 


Recall that $\log(n) &lt; n^\epsilon$ for any constant $\epsilon&gt;0$ when $n$ is large enough.
Show that $\displaystyle\lim_{n\to\infty}\frac{\log(\frac{n\log\log(n)}{\log(n)})}{\log(n)}=1$.
Show that $\displaystyle\lim_{n\to\infty}\frac{\log\log(\frac{n\log\log(n)}{\log(n)})}{\log\log(n)}=1$.


Exercise 2. Show that $g(n)−f(n)=O(1)$. (This exercise might be hard.)