math - solving T(n) = 4T(n/2) + n^3 + n*(log(n))^2 -

i trying solve recurrence using substitution method. recurrence relation is:

t(n) = 4t(n/2) + n^3 + n*(log(n))^2 

i tried solve master method.

first supstitution can use n = 2^k. recurrence becomes:

t(2^k) = 4t(2^(k-1)) + 2^(3k) + 2^k * log(2^k)^2

or

t(2^k) = 4t(2^(k-1)) + 2^(3k) + c * k^2 * 2^k

where c = (log 2)^2.

after supstitution, s(k) = t(2^k) , dividing 4^k get

s(k) / 4^k = s(k-1) / 4^(k-1) + 2^k + c * k^2 / 2^k

our final supstitution r(k) = s(k) / 4^k , new recurrence is

r(k) = r(k-1) + 2^k + c * k^2 / 2^k

by telescoping (ie. summing these equations k = 2, 3, ..., n) get

r(n) = r(1) + sum(2^k) + c * sum(k^2 / 2^k)

(where both sums go k = 1 k = n - 1).

finally,

r(n) = r(1) + 2^n - 1 + c * (6 - (n^2 + 2n + 3) / 2^(n-1)).

t(2^k) can found last equation. other values of t(n) (when n not power of 2), don't have enough data without additional assumptions (continuity, example).