5 votes 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 asked Jun 24, 2017 • retagged Jul 8, 2022 by Lakshman Bhaiya sumit_kumar 952 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply joshi_nitish commented Jun 24, 2017 reply Follow Share is it 2^nT(na/b) in R.H.S?? 0 votes 0 votes sumit_kumar commented Jun 24, 2017 reply Follow Share 2^n T(n/2) + n^n 0 votes 0 votes joshi_nitish commented Jun 24, 2017 reply Follow Share O(n^nlogn)?? answer could be less than this but will never exeed it.. 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes Answer Arnab Bhadra answered Jun 24, 2017 Arnab Bhadra comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments joshi_nitish commented Jun 24, 2017 reply Follow Share 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 votes 0 votes Arnab Bhadra commented Jun 25, 2017 reply Follow Share @sumit you cannot solve it by master theorem as a is not constant. 1 votes 1 votes aehkn commented Aug 6, 2017 reply Follow Share Second level complexity may be 2n*(n/2)n/2 why you consider each complexity as (n/2)n 0 votes 0 votes Please log in or register to add a comment.
