5 5 votes What will be the time complexity for the following equation: $$T(n)= 2^{n} T(\frac{n}{2}) +n^{n}$$ Algorithms algorithms time-complexity recurrence-relation + – sumit_kumar 1.8k views answer comment Share Follow Print See all 3 Comments 3 3 Comments reply joshi_nitish commented Jun 24, 2017 reply Follow flag is it 2^nT(na/b) in R.H.S?? 0 0 replyShare sumit_kumar commented Jun 24, 2017 reply Follow flag 2^n T(n/2) + n^n 0 0 replyShare joshi_nitish commented Jun 24, 2017 reply Follow flag O(n^nlogn)?? answer could be less than this but will never exeed it.. 0 0 replyShare Please log in or register to add a comment.
3 3 votes Answer Arnab Bhadra answered Jun 24, 2017 Arnab Bhadra comment Share Follow See all 6 Comments 6 6 Comments reply srestha commented Jun 24, 2017 i edited by srestha Jun 24, 2017 reply Follow flag .......... 0 0 replyShare sumit_kumar commented Jun 24, 2017 reply Follow flag But acc to master's theorem rule "a" must be a constant ? correct me if I'm wrong. 0 0 replyShare srestha commented Jun 24, 2017 reply Follow flag yes cannot be solved by master theorem 0 0 replyShare joshi_nitish commented Jun 24, 2017 reply Follow flag in second level it will be 2^n*((n/2)^(n/2))....and in third level it will 2^n*2^(n/2)*(n/4)^(n/4)....and so on... your answer is correct but, it might have more tight upper bound... 0 0 replyShare Arnab Bhadra commented Jun 25, 2017 reply Follow flag @sumit you cannot solve it by master theorem as a is not constant. 1 1 replyShare aehkn commented Aug 6, 2017 reply Follow flag Second level complexity may be 2n*(n/2)n/2 why you consider each complexity as (n/2)n 0 0 replyShare Please log in or register to add a comment.
