Zeal Indore

Question

Compute: T(n) = 2^nT(n/2) +n^n

1)theta(n^n)

2)theta(nlogn)

3)theta(n^nlogn)

4)none of these.

Comments

option (A)?

Answer 1

According to master theorem - 

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

There are following three cases:
1. If f(n) = Θ(n^c) where c < Log_ba then T(n) = Θ(n^Log_ba)

2. If f(n) = Θ(n^c) where c = Log_ba then T(n) = Θ(n^cLog n)

3.If f(n) = Θ(n^c) where c > Log_ba then T(n) = Θ(f(n))

1.  a = 2^n
2. b = 2
3. c = n
4. c = Log_ba
5. T(n) = Θ(n^cLog n)

so T(n) = Θ(n^n Log n)

Comments

sorry, but we cannot apply master theorem here as "a" is not constant. 

check for ref : https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Inadmissible_equations