The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
98 views
$\Large T(n) = 2^nT(\frac{n}{2}) + n^n$
asked in Algorithms by Boss (34.6k points) | 98 views
0
Is $T(1)=1?$
0

 yes

0
0
$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

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

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

It is an exponential func.
0
We cant apply master theorem because a is not constant here

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,814 questions
54,522 answers
188,364 comments
75,391 users