I am applying substitution method to find the time complexity of the following recurrence relation. But I am having difficulty solving it past a certain point.
$$T(n) = 2^n T(n/2) + n^n$$
After substituting $T(n/2)$: $$T(n/2) = 2^\frac{n}{2} T(n/4) + (n/2)^\frac{n}{2}$$
I get, $$T(n) = 2^\frac{3n}{2}T(n/4) + n^n + 2^\frac{n}{2}n^\frac{n}{2}$$
I further substitute $T(n/4)$ and get:
$$T(n) = 2^\frac{7n}{4}T(n/8) +n^n + 2^\frac{n}{2}n^\frac{n}{2} + 2^\frac{2n}{4}n^\frac{n}{4}$$
Thus after generalizing:
$$T(n) = 2^\frac{2k-1}{2^{k-1}}T(n/2^k) + \sum_{i=0}^{\infty}2^\frac{in}{2}n^\frac{n}{2^i}$$
Can someone help me with the summation: $$\sum_{i=0}^{\infty}2^\frac{in}{2}n^\frac{n}{2^i}$$
Or suggest some easier way to solve this recurrence relation.