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

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.

• I dont think your "after generalizing" is correct. The term $2^{\frac{in}{2}}$ is a bit fishy - I don't think it is correct even at i=2 or i=3. Nov 25, 2021 at 14:34
• I don't see any time complexity here. Nov 25, 2021 at 16:40
• @nirshahar okay, I'll check it once. Nov 26, 2021 at 4:45

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.