用代入法求解递归关系 T(n) = 8T(n/4) + (n^2)*logn

Question

我们需要像这个例子一样解决它

if T(n/2) = 4T(n/(2^2)) + ((n/2)^2)*log (n/2)  ----> 1,
   T(n/4) = 4T(n/(2^3)) + ((n/4)^2)*log (n/4)  ----> 2
   and
   T(n/8) = 4T(n/(2^)4) + ((n/8)^2)*log (n/8)  ----> 3,


T(n) = 4T(n/2) + (n^2)*log n
T(n) = 4[4T(n/(2^2)) + ((n/2)^2)*log (n/2)] + (n^2)*log n  ----> replace 1 with T(n/2)
T(n) = (4^2)T(n/4) + (n^2)*log (n/2) + (n^2)*log n
T(n) = (4^2)[4T(n/(2^3)) + ((n/4)^2)*log (n/4)] + (n^2)*log (n/2) + (n^2)*log n ----> replace 2 with T(n/4)
T(n) = (4^3)T(n/8) + (n^2)*log (n/4) + (n^2)*log (n/2) + (n^2)*log n ----> replace 3 with T(n/8)
T(n) = (4^3)[4T(n/(2^)4) + ((n/8)^2)*log (n/8)] + (n^2)*log (n/4) + (n^2)*log (n/2) + (n^2)*log n
T(n) = (4^4)T(n/16) + (n^2)*log (n/8) + (n^2)*log (n/4) + (n^2)*log (n/2) + (n^2)*log n

if this goes till k,

T(n) = (4^k)T(n/(2^k)) + (n^2) (log (n/8) + log (n/4) + log (n/2) + log n)

if n/(2^k) = 1, n = 2^k, k = log n and T(1) = 1,

T(n) = (n^2)T(1) + (n^2) (log ((n/(2^k)......(n/(2^3)) * (n/(2^2)) * (n/(2^1)) * n)
T(n) = (n^2)T(1) + (n^2) (log ((n/(2^log n)......(n/(2^3)) * (n/(2^2)) * (n/(2^1)) * n)
T(n) = (n^2) + (n^2) (log (2^logn)) (Using geometric series)
T(n) = O(n^2 log n)

一定数量的步骤后不能简化方程式。