Find Asymptotic upper bound (http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf)

Question

$\Large T(n) = 2^nT(\frac{n}{2}) + n^n$

Comments

Is $T(1)=1?$

---

srestha yes

---

https://www.quora.com/How-do-I-solve-the-recurrence-relation-T-n-n-1-2-T-n-1-2-+-n-1-2-using-the-substitution-method

this may help

but less chance in compititive exam

right?

---

$T\left ( n \right )=2^{n}T\left ( \frac{n}{2} \right )+n^{n}$

                         $=2^{n}\left ( 2^{n/2}T\left ( \frac{n}{2^{2}} \right )+\left ( \frac{n}{2} \right ) ^{n/2}\right )+n^{n}$

                        $=2^{n+\frac{n}{2}+\frac{n}{4}+........}T\left ( 1 \right )+n^{n}+\left ( \frac{n}{2} \right )^{n/2}+\left ( \frac{n}{4} \right )^{n/4}+.......1$

                          $=2^{n}+n^{n}+............$

                           $=O(n^{n})$

---

@srestha why can't we use master theorem here.using that ans comes out $n^{n}logn$

---

no, we cannot apply master theorem because f(n) is not polynomial function here

It is an exponential func.

---

We cant apply master theorem because a is not constant here

---

These may help

https://www.geeksforgeeks.org/advanced-master-theorem-for-divide-and-conquer-recurrences/

Answer 1

$T(n)=O(n^n logn)$