Finding the asymptotic complexity class of $T(n) = 2T(n/2) + (n/\lg n)$

Question

I've been trying to figure out how to solve this for a while. We are currently learning the master theorem, and the above recurrence is in my homework. I've tried applying it and found that it can't be used here. So I've started to expand the recurrence out by iteration and got this: $$T(n)=2^k\cdot T\left(\frac n{2^k}\right)+(2^k-1)\left(\frac n{\lg n}\right)$$ If I let $2^k=n$ and $T(1)=1$ I get $$T(n)=n+(n-1)\left(\frac n{\lg n}\right)$$ which leads to $$T(n)=n+\left(\frac{n^2-n}{\lg n}\right)$$ I don't know where to go from here. How would I classify this function's asymptotic complexity?

Answer 1

For things like $T(n) = 2T(n/2) + (n/\lg n) $, I throw $n = 2^m$ or even $n = 2^{2^m}$ at it and see what sticks.

If $n = 2^m$, this becomes $T(2^m) = 2T(2^{m-1}) + (2^m/m) $.

Letting $T(2^k) = s(k)$, we get $s(m) = 2s(m-1)+2^m/m$.

Doing the usual, which, in this case, is dividing by $2^m$, this becomes $\frac{s(m)}{2^m} = \frac{s(m-1)}{2^{m-1}}+1/m$.

Letting $r(m) = \frac{s(m)}{2^m}$, this becomes $r(m) = r(m-1)+1/m$ or $r(m) - r(m-1)=1/m$.

Summing from $1$ to $N$, $r(N)-r(0) =\sum_{m=1}^N 1/m \approx \ln N $.

So $r(N) \approx \ln N$. (I may worry about the constant later.)

Working backwards, $s(m)=2^mr(m) \approx 2^m \ln m $.

Therefore $T(2^k) = s(k) \approx 2^k \ln k$ or, replacing $2^k$ by $j$, $k = \lg j$ so that $T(j)\approx j \ln \lg j $, which is Did's result in their comment.

WHen I get this type of result, I know that it needs a more rigorous derivation (in particular, about the $n$ which are not of the form $2^m$ as well as neglected constants), but I am usually pretty comfortable stating that this is the true size of the terms.