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?

  • 2
    $\begingroup$ Not sure how you got $T(n) = 2^k * T(\frac{n}{2^k}) + (2^k - 1)(\frac{n}{\lg(n)})$, which seems wrong and probably uses false identities involving the logarithm -- but anyway one can throw the M***er theorem to the bin and simply note that $2^{-k}T(2^k)=2^{-(k-1)}T(2^{k-1})+(k\log2)^{-1}$ hence $2^{-k}T(2^k)=(\log2)^{-1}H_k+T(1)=\Theta(\log k)$ (where $H_k$ denotes the $k$th harmonic number), which yields $T(2^k)=\Theta(2^k\log k)$, from which you might be asked to deduce (although there is no way this can be deduced rigorously) that $T(n)=\Theta(n\log\log n)$. $\endgroup$ – Did Sep 30 '16 at 19:42
  • $\begingroup$ If your last line is correct, you are done. The dominant term is $\frac {n^2}{\lg n}$ so that is the complexity class. This is strictly less than, but not much less than, $n^2$, so if you have a restricted list of classes you are probably in $n^2$ $\endgroup$ – Ross Millikan Oct 1 '16 at 5:13

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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