How to Solve Recurrence Relations When Master Theorem is not Applicable

Question

How to mathematically solve the recurrence relations of the following form :

1. T(n)=(2^n)T(n/2) + n^n
2. T(n)=4T(n/2) + n^(2)/logn

Is there a generic method to solve these?

I realize that master theorem is not applicable on these forms because in 1, 2^n is not a constant and 2 does not fall into any of the 3 cases of the master theorem.

Answer 1

Choosing a path base as n = 2^m we have the recurrence

T(2^m) = 2^(2^m)T(2^(m-1)) + (2^m)^(2^m)

Calling now TT(.) = T(2^(.)) we follow with

TT(m) = 2^(2^m)TT(m-1) + (2^m)^(2^m)

This is a linear recurrence easily solved as

TT(m) = 4^(2^m-2)(c0 + sum[2^(4-2^(k+2))*(2^(k+1))^(2^(k+1)),(k,0,m-1)])

now going backwards with m = log(2,n) we get at

T(n) = 4^(n-2)(c0 + sum[2^(4-2^(k+2))*(2^(k+1))^(2^(k+1)),(k,0,log(2,n)-1)])

or

T(n) = 4^(n-2)c0 + n^n + 2^(n/2)n^(n/2) + ... +

The second recurrence can be solved following the same process.