I have the following recurrence relation:
$$T(n) = 64T(\frac n8) − n^2\log{n}$$
Now the solution manual says it's not solvable as $f(n)$ is not positive when compared with master method though we can see that:
$$T(n) = 64T(\frac n8)+n^2(\log{n})^-1$$
So, we can see that $log_b(a) = 2 = k$, so we have CASE II. Since $p=-1$, then we have $O(n^2\log\log{n})$, but again solution says it's not solvable, what do you think please?
Best Answer
Hint.
The formal recurrence
$$ T(n) = a^2 T\left(\frac na\right)-n^2 \ln n $$
can be handled as follows
$$ T\left(a^{\log_a n}\right) = a^2T\left(a^{\log_a \frac na}\right)-n^2 \ln n $$
Calling now $\mathcal{T}(\cdot) = T\left(a^{(\cdot)}\right) $ and $z = \log_a n$ we follow with
$$ \mathcal{T}(z) = a^2 \mathcal{T}(z-1)-a^{2z}z\ln a $$
with solution
$$ \mathcal{T}(z) = a^{2z}\left(c_0 -\frac 12 z(z+1)\ln a\right) $$
now to recover $T(n)$ we go backwards with $z = \log_a n$