Finding time complexity $T(n) = 2^n T(n/2) + n^n$

Question

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.

Answer 1

We prove by induction that $T(n) \leq Cn^n$, where $C = \max(T(2),4/3)$. The base cases are clear. For the inductive case, $$ T(n) = 2^nT(n/2) + n^n \leq C2^n (n/2)^{n/2} + n^n = C\left(\frac{2}{n}\right)^{n/2} n^n + n^n \leq (C/4 + 1)n^n \leq Cn^n. $$ On the other hand, clearly $T(n) \geq n^n$. Hence $T(n) = \Theta(n^n)$.

In fact, if we work a bit harder, we find out that $T(n) = (1 + o(1)) n^n$. Working even harder, we can obtain the even more accurate estimate $T(n) = n^n + (1+o(1)) (2n)^{n/2}$; and so on.