Solving recurrences

It is true, the Master theorem does not apply.

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

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

Then ng(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) = ng(n) = Theta(nlog logn.)

You guessed it right.

If you use a tree to visualize the question, you'll see that the sum of each rank is:

• rank 0:

(which is equal to n/log(n)) - rank 1:

and so forth, with a general sum of n/log(n/(3^i)) for each rank, i being the current rank. so, all together we get:

if we open the equation we get:

(starting from the end and going backwards.. first when i=log(base3)n and then going back)

since log base doesn't matter in theta, we get :

which is:

which is (in sigma):

which is a harmonic series, equal to:

and since ln is log with a base of e, and log bases don't matter in theta, we finally get:

which is equal to:

so, it's theta(n log log n).