# Solving $T(n) = 2T(n/2) + T(n-1)/\log n$

I am interesting in the asymptotic rate of growth of the following recursion:

$$T(n) = 2T(n/2) + \frac{T(n − 1)}{\log n},$$ with base case $$T(1) = 1$$.

I'm having trouble of solving this recurrence problem, it seems much more tricky than I initially thought, and I'm totally stuck after doing some unrolling. What is a good way to approach this question?

• Do you have a guess on the solution of the recurrence? Nov 4 '19 at 19:28
• I'm guessing nlogn but not sure how to verify it. Nov 4 '19 at 19:39

By comparison to the recurrence $$T(n) = 2T(n/2)$$, we see that $$T(n) = \Omega(n)$$. By comparison to the recurrence $$T(n) = 2T(n/2) + n$$, we see that actually $$T(n) = \Omega(n\log n)$$.
Now let us prove by induction that the other direction holds as well. I will interpret $$T(n/2)$$ as $$T(\lfloor n/2 \rfloor)$$. Suppose that $$T(m) \leq Cm\log m$$ for all $$m < n$$. Then $$T(n) \leq 2C\frac{n}{2}\log \frac{n}{2} + \frac{n\log n}{\log n} = Cn\log n + (1-C)n.$$ For $$C \geq 1$$, it follows that $$T(n) \leq Cn\log n$$.
It seems that we have proved that $$T(n) = O(n\log n)$$, but actually the base case of the induction doesn't hold. However, this shouldn't be too hard to fix (left to the reader).