1
$\begingroup$

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)$?

$\endgroup$
1
  • $\begingroup$ The terms in your summation are not correct. $\endgroup$
    – user16034
    Aug 31, 2022 at 10:06

1 Answer 1

1
$\begingroup$

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).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.