what is the closed form of the recurrence : T(n) = aT(n/2) + dn^n

Question

i am trying to solve the recurrence $T(n) = aT(n/2) + dn^n$. and here is my trial::

$n^{log_b(a)} = n^{lg(a)}$ since $b=2$

But $n^n/{n^{lg(a)}}= n^{n-lg(a)}$ is NOT polynomially bounded and therefore Master Theorem can't be applied. so, i use the recursion tree method and i end with the followinf recurrence ::

$T(n) = d\sum a^id(n/2^i)^{n/2^i} + \theta(n^{lg(a)})$ where $i = 0: lg(n) - 1$

is that true ?? and if it is , what is the closed form of this summation ?

Thanks in advance

Answer 1

$n^n$ is really, really big; nothing else in the problem matters.

$$ T(n) = \Theta(n^n) $$

Once you realize that, the problem is fairly straightforward.

---

Incidentally, this is coverred by some forms of the Master theorem, such as case three at wikipedia