Search code examples
algorithmrecurrencemaster-theorem

Method to solve the stated recurrence?

Need help finding a method for solving the following:
Given f(n) to be 9f(n/3)+(n2)*(log3n) for all n > 1.
And given f(1)=1.
Solve for f(n)
I tried the master theorem, but all the 3 cases did not fit here, my guess would be using the substitution method, but I am not sure how to apply it

Solution

  • Use the substitution f(n) = n2g(n).

    This gives us g(n) = g(n/3) + log n.

    And so g(n) = Θ(log2n) and f(n) = Θ(n2log2n)