Search code examples
algorithmmathrecursionasymptotic-complexity

Solving recurrences

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

Solution

  • 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.