Recurrence: T(n) = (2+1/log n)T(n/2)

Question

I have to solve this recurrence relation with tree method, because Master theorem does not apply.

T(n) = (2+1/log n) T(n/2)

Answer 1

After a some thoughts I can not come up with an exact solution. Master's theorem does not work here and unrolling the tree has not gave me anything reasonable. So I will just estimate the complexity in the following way.

For any reasonably big n you can estimate 0 < 1/log n < 1. So you can get:

T1(n) = 2 * T1(n/2)
T2(n) = 3 * T2(n/2)

and O(T1) < O(T) < O(T2). You can find the complexity for both recurrences using master theorem. The complexity of T1 is O(n) and of T2 is O(n^log2(3)).

So you can be sure that the complexity of your recurrence is bigger than O(n) and less than O(n^1.58), so less than quadratic.