1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Nov 25, 2021 at 14:34
  • $\begingroup$ I don't see any time complexity here. $\endgroup$ Nov 25, 2021 at 16:40
  • $\begingroup$ @nirshahar okay, I'll check it once. $\endgroup$ Nov 26, 2021 at 4:45

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.