Solve the following Recurrence using any method

Question

T(n) = 2ⁿ T $(\frac{n}{2})$ + nⁿ

Comments

is answer o(n^{n) ....?}

---

I  beg you mam please post your answer.

---

firstly..pls dun say like this..please.

and secondly i guessed nⁿ because evrytime nⁿ work is done,and nⁿ has the highest asymptotic complxeity.

so thats why i thot so,i might be incorrect.i have not solved it.

what is the answer ??

---

Mam please solve using any method and just tell answer and post whatever your answer is coming either iteration or recursion tree will only work in this question.because master fails and there is no other option than these two methods

Answer 1

Here r d steps though I m getting a different answer. 

I've solved dis equation using d Master's Theorem. You can verify d descp. Yeah. :)

Give equation is of d form:

aT(n/b)+f(n)

Here given equation is:

2ⁿ(n/2)+nⁿ.

So a=2ⁿ, b=2, f(n)=nⁿ

Now a=2ⁿ, b=2

Keeping it in log_ba, we have log₂2ⁿ ,

So we get nlog₂2 which equals n, since(log₂2=1). 

Now nⁿ thru d form n^log_ba. 

So n^log_ba  is equal to d case II of Master's Theorem. 

So T(n) time complexity is given by 

T(n)=θ(nⁿ log₂n)

is d final answer. :)

Comments

i don't think masters theorem is applicable for this one as 'a' has to be a constant it has to greater than or equal to 1

---

Give equation is of d form:

aT(n/b)+f(n)

Here a should be constant value and it should be greater than equal to 1. 

T(n) = 2ⁿ T $(\frac{n}{2})$ + nⁿ

Here a is 2ⁿ and this is not a contant value hence Master Thoerem cannot be applied at all .

---

T(n)=O(nlogn)

is the complexity

Answer 2

Is it O(2^(n^(log2(n)-1)) ?? Or it is near to the answer ??

Comments

dear sir you please take snapshot through mobile and please kindly post that over here please

---

@Arjun Sir,Kindly intervene here.D solution is causing a lil bit confusion.

---

hey @LavTheRawkstar I thought of the problem using recursion tree and it is coming O(n^n)

Answer 3

Solve it by using recursive tree method.. You will get n^n cost at each level and tree grows upto logn therefore O(n^n logn)