I have got this recurrence relation: $T(n) = (2^n)T(n/2) + (n^n)$
This cannot be solved using Master's Theorem (for $T(n) = aT(n/b) + O(n^k)$) because $a$ is not constant but depends on $n$.
Below is my approach to this problem (trying using Recurrence Relation):
$T(n) = 2^nT(n/2) + n^n \\ \\ = 2^n[2^{n/2}T(n/2^2) + (n/2)^{n/2}] + n^n \\ \\ = 2^{n(1+1/2)}T(n/2^2) + (2n)^{n/2} + n^n \\ \\ = 2^{n(1+1/2+1/2^2)}T(n/2^3) + 2^nn^{n/4} + (2n)^{n/2} + n^n$
As shown in the last line, I cannot find any closed mathematical form for the terms after T(n/8).
Assume: T(1) = c