Search code examples
algorithmrecurrencemaster-theorem

Time complexity of T(n) = 27T(n/3) + (n^3)log(n)

I need some help with this recurrence. I tried it by myself and I got teta( (n^3)logn) but Wolfram Alpha says this:

recursion

I guess this is like an O( (n^3) log^2(n)). I can't use master theorem, so I solved it by recurrence. This is my solution, but I don't know what's wrong with it

manual solution

Solution

  • You made a mistake in the last stage. Using these properties: log(x) + log(y) = log(xy) and log(x/y) = log(x) - log(y) and log(x^y) = y log(x)`, we have the following:

    sum_{i=0}{k-1} log(m/3^i) = log(m^k / (1 * 3 * 3^2 * ... * 3^(k-1))) 
= log(m^k) - log(3^((k-1)k/2)) 
= k log(m) - (k-1)k/2 log(3) = c * k * (k-1) = Theta(log(m) * log(m))

    Therefore, the time complexity is m^3 log^2(m).