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
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)