<s>[INST] A Recurrence Relations problem I need to bound
$$T(n) = 2T\left(\frac{n}{2}\right) + n\cdot \frac{\log \log n}{\log n}$$ as tight as possible.
Here is what I got:
Firstly, we introduce a change of variable. Let $n = 2^k$ while ignoring the rounding, then we have
$$
 T(n) = T(2^k) =: g(k).
$$
Expand it further, we get
$$
 \begin{split}
  g(k) &= 2\cdot g(k-1) + 2^k\cdot \frac{\log \log 2^k}{\log 2^k}\\
  &= 2\cdot g(k-1) + 2^k\cdot \frac{\log k}{k}\\
  &= 2\cdot \left(2\cdot g(k-2) +  2^{k-1}\cdot \frac{\log k-1}{k-1}\right) + 2^k\cdot \frac{\log k}{k}\\
  &= 2^2\cdot g(k-2) +  2^{k} \left(\frac{\log k-1}{k-1}\right) + 2^k\cdot \frac{\log k}{k}\\
  &= 2^2\cdot g(k-2) +  2^{k} \left(\frac{\log k-1}{k-1} + \frac{\log k}{k}\right)\\
 \end{split}
$$
By induction, we see that
$$
 g(k) = 2^{k - 1} g(1) + 2^k\left(\sum\limits_{i=0}^{k-1} \frac{\log k-i}{k-i}\right)
 = 2^{k - 1} + 2^k\left(\sum\limits_{i=0}^{k-1} \frac{\log k-i}{k-i}\right)
$$
since $g(1) = T(2) = 1$ by assumption. Let $k-i := j$, we further have
$$
 g(k) = 2^{k - 1} + 2^k\sum\limits_{j = 1}^{k} \frac{\log j}{j}.
$$
Substitute $k$ back to $n$, we have
$$
 T(n) = \frac{n}{2} + n\sum\limits_{k = 1}^{\log n} \frac{\log k}{k}.
$$
In order to bound the sum, we investigate $\frac{\log x}{x}$. We see that
$$
 \left(\frac{\log x}{x}\right)^\prime = \frac{1 - \log x}{x^2},
$$
which is $0$ when $x = 2$, and positive in $(0, 2]$ while negative in $[2,+\infty)$ assuming base $2$. By taking the second derivative,
we see that it's negative at $2$, hence we conclude that it reaches its maximum at $2$ with the value $\frac{1}{2}$. Hence, we have
$$
 T(n) = \frac{n}{2} + n\sum\limits_{k = 1}^{\log n} \frac{\log k}{k} \leq \frac{n}{2} + n \log n\cdot \frac{1}{2} = O(n\log n).
$$
As one can see, the main problem in this derivation is to bound the summation
$$
\sum\limits_{k = 1}^{\log n}\frac{\log k}{k},
$$
which I can't think of a better bound. It's clearly too large since I simply take the maximum of $\frac{\log x}{x}$ while $\frac{\log x}{x}$ is rapidly decreasing. Are there any formula I can use for improving this bound?
 [/INST] Here I will present a bound for the sum
$$\sum_{j=1}^k \frac{\log j}{j}.$$
The basic idea is that the partial sum can be asymptotically approximated by the integral of the function $\frac{\log x}{x}$, which is easy to compute. More generally, if a function $f(x)$ is decreasing on $[a,\infty)$, then the following bounds hold.
$$f(b) + \int_a^b f(x)\ dx  \leq \sum_{j=a}^b f(j) \leq f(a) + \int_a^b f(x)\ dx $$
This can be seen by drawing a picture and considering the left and right Riemann sums of step size $1$.
The function $(\log x)/x$ is zero at $x = 1$ and decreasing for $x \geq 3$, so we can approximate the sum like so:
\begin{align*}
\sum_{j=1}^k \frac{\log j}{j} &= \frac12 \log 2 + \sum_{j=3}^k \frac{\log j}{j}\\
&\leq \frac12 \log 2 + \frac13 \log 3 + \int_3^k \frac{\log x}{x}\ dx\\
&= \frac12 \log 2 + \frac13 \log 3 + \Big( \frac12\log^2 x \Big)\Big|_{x=3}^k\\
&= \frac12 \log 2 + \frac13 \log 3 + \Big(\frac12\log^2 k - \frac12\log^2 3\Big)\\
&\approx \frac12\log^2 k +0.1093\ldots\\
&\leq \frac12\log^2 k + 0.11
\end{align*}
Here I have assumed that the logarithm in use is the natural logarithm, but you can convert to another logarithm by dividing through by the appropriate change of base constant. At the very least, it shows that
$$\sum_{j=1}^k \frac{\log j}{j} = \mathcal O (\log^2 k)$$
which may be sufficient. Here is a plot of the asymptote.
</s>