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

Question

I am trying to solve a recurrence by using substitution method. The recurrence relation is:

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

I tried to solve this also with master method.

Answer 1

First supstitution you can use is n = 2^k. Your 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 another supstitution, S(k) = T(2^k) and dividing by 4^k we get

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

Our final supstitution is R(k) = S(k) / 4^k and the new recurrence is

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

By telescoping (ie. summing these equations for k = 2, 3, ..., n) we get

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

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

Finally,

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

T(2^k) can easily be found from the last equation. For other values of T(n) (when n is not a power of 2), you don't have enough data without additional assumptions (continuity, for example).

Answer 2

From the point of view of a time complexity, T(n) = 4T(n/2) + n^3 + n*(log(n))^2 is the same as T(n) = 4T(n/2) + n^3.

Now using a master theorem, you have a=4, b=2 and therefore c = logb(a) = 2. Because n^c grows slower than your f(n) = n^3, you fall into the third case and the time complexity is O(n^3)