Solve the recurrence $T(n)=T(\frac{n}{2})+\frac{n}{\log n}$ without master theorem

Question

Suppose given the recurrence $$T(n)=T(\frac{n}{2})+\frac{n}{\log n}.$$ I think the answer is $$T(n)=O\left(\frac{n}{\log n}\right).$$ because $$T(n)=T(1)+\sum_{i=0}^{\log n-1} \frac{n}{2^i(\log n-i)}$$ but how we can show that $\sum_{i=0}^{\log n-1} \frac{n}{2^i(\log n-i}=O\left(\frac{n}{\log n}\right)$?

Answer 1

With $n:=2^m$, the recurrence turns to

$$S(m)=S(m-1)+\frac{2^m}m$$

and

$$S(m)=S_0+\sum_{k=1}^m\frac{2^k}k.$$

Splitting the sum and keeping the smallest denominators, we get $$S_0+\sum_{k=1}^{m/2-1}\frac{2^k}k+\sum_{k=m/2}^m\frac{2^k}k\le S_0+\sum_{k=1}^{m/2-1}2^k+\frac 2m\sum_{k=m/2}^m2^k\\=O\left(2^{m/2}+\dfrac{2^m}m\right)=O\left(\frac{2^m}m\right).$$

Then indeed

$$T(n)=O\left(\frac n{\log n}\right).$$