Solving recurrences

Question

Am trying to solve the given recursion, using recursion tree, T(n) = 3T(n/3) + n/lg n.

In the first level (n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3)).

In the second level it turns out to be n/(log(n/9)).

Can I generalize the above equation in the form of n.loglogn

This is a general doubt I've, I need an insight on this.

Note: Any function that has to be Theta(n^k log^k (n)) in that function k should >=1. And in this case k is -1 so master theorem doesn't come in to picture

Answer 1

It is true, the Master theorem does not apply.

T(n) = 3T(n/3) + n/logn.

Let g(n) = T(n)/n.

Then n*g(n) = 3*(n/3)*g(n/3) + n/logn.

Thus

g(n) = g(n/3) + 1/log n.

This gives g(n) = Sum 1/log n + 1/log n/3 + 1/log n/9 + ...

= Theta(Sum 1/logn + 1/(logn -1) + 1/(log n - 2) + ...) = Theta(Integral 1/x between 1 and logn) = Theta(log log n).

Thus T(n) = n*g(n) = Theta(n*log logn.)

You guessed it right.