I was trying to prove that if $$f(n) = \sum_{i=1}^{n}\frac{n}{i} \log\frac{n}{i} $$ $$g(n) = n \log^2n$$ then $O(f(n)) = O(g(n))$
I am not sure that it is the case, but based on my simulation $$\lim_{n \to \infty }\frac{f(n)}{g(n)} \approx 0.536...$$ and slightly decreasing with increase of $n$.
I tried to tackle the problem by using induction. I started with some basic case and tried to prove that if this one is correct, the next one will be correct as well (which left me nowhere). I tried the same approach but instead of proving that $n+1$ will be correct I tried to prove that $2n$ will be correct (I want to show that asymptotic holds, so I thought that this is ok). The second approach also failed.
What is the right approach to this problem (or may be $O(f(n))$ is not $O(g(n))$). If my guess is correct it would be also nice to know if there is a value for the limit.
Hint. One may recall that, by the Euler-Maclaurin formula, as $n \to \infty$, we have $$ \begin{align} \sum_{i=1}^n \frac 1i &=\ln n+\gamma+\mathcal{O}\left( \frac 1n\right)\\ \sum_{i=1}^n \frac {\ln i}i &=\frac 12\ln^2 n+\gamma_1+\mathcal{O}\left( \frac {\ln n}n\right) \end{align} $$ where $\gamma$ is the Euler-Mascheroni constant and $\gamma_1$ is the Stieltjes constant.
Then we may write, as $n \to \infty$: $$ \begin{align} f(n) &=\sum_{i=1}^n \frac {n}i \ln\frac {n}i\\\\ &=n \ln n \sum_{i=1}^n \frac 1i -n \sum_{i=1}^n \frac {\ln i}i\\\\ &=n \ln n \left(\ln n+\gamma+\mathcal{O}\left( \frac 1n\right) \right) -n \left(\frac 12\ln^2 n+\gamma_1+\mathcal{O}\left( \frac {\ln n}n\right)\right)\\\\ &=\frac n2\ln^2 n+\gamma \:n \ln n-\gamma_1\:n+\mathcal{O}\left( \ln n \right) \end{align} $$ In particular, you have $f(n)=\mathcal{O}(n\ln^2 n)$ and since $g(n)=n\ln^2 n$, you obtain $$ \mathcal{O}\left(f(n)\right) = \mathcal{O}\left(g(n)\right), $$ as announced.