Solve T(n) = 2T(n/2) + n/log n for n >= 2, with T(1) = 1. State the tight bound and say why the master theorem does not settle it.

Solve T(n) = 2T(n/2) + n/log n for n >= 2, with T(1) = 1. State the tight bound and say why the master theorem does not settle it.

Approach: Compare f(n) against n^{log_b a} first, then sum the recursion tree level by level and recognise the harmonic sum.

Theta(n log log n). Here a = 2, b = 2 so n^{log_b a} = n, and f(n) = n/log n is smaller than n by only a logarithmic factor, so the polynomial gap that case 1 of the master theorem requires does not exist and no case applies. Sum the recursion tree instead. At depth i there are 2^i subproblems of size n/2^i, each costing (n/2^i)/log(n/2^i), so the level cost is n/(log n - i). Summing over the levels from the root down to depth log n - 1 gives n * (1/log n + 1/(log n - 1) + ... + 1/1), which is n times the harmonic sum H(log n). Since H(m) ~ ln m, the total is Theta(n ln log n), that is Theta(n log log n).

Follow-up: What is the bound if the driving term is n/(log n)^2 instead, and why does the answer become linear?

Key concepts: master theorem, recursion tree, harmonic sum, polynomial gap.