1 votes 1 votes $\Large T(n) = 2^nT(\frac{n}{2}) + n^n$ Algorithms asymptotic-notation time-complexity + – Mk Utkarsh asked Apr 19, 2019 Mk Utkarsh 949 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply srestha commented Apr 19, 2019 reply Follow Share Is $T(1)=1?$ 0 votes 0 votes Mk Utkarsh commented Apr 19, 2019 reply Follow Share srestha yes 0 votes 0 votes srestha commented Apr 19, 2019 reply Follow Share 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? 0 votes 0 votes srestha commented Apr 19, 2019 reply Follow Share $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})$ 0 votes 0 votes a new one commented Apr 21, 2019 reply Follow Share @srestha why can't we use master theorem here.using that ans comes out $n^{n}logn$ 0 votes 0 votes srestha commented Apr 21, 2019 reply Follow Share no, we cannot apply master theorem because f(n) is not polynomial function here It is an exponential func. 0 votes 0 votes Anuranjan commented Jun 21, 2019 reply Follow Share We cant apply master theorem because a is not constant here 0 votes 0 votes omzzz commented Dec 16, 2020 reply Follow Share These may help https://www.geeksforgeeks.org/advanced-master-theorem-for-divide-and-conquer-recurrences/ 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes $T(n)=O(n^n logn)$ okntk answered Apr 15, 2023 okntk comment Share Follow See all 0 reply Please log in or register to add a comment.