How to mathematically solve the recurrence relations of the following form :
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.
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.
