0

$t(n)=2^nt(n/2)+n^n$

I can't use Master Theorem becaus $2^n$ and althought I am familiar with other Recursive Tree method, I can't solve it. Is there a chance solve it using Recursive Tree method?

Furkan Ergün
  • 1

2 Answers2

0

One approach $$ \begin{split} t_n &= 2^n t_{n/2} + n^n \\ &= 2^n \left[2^{n/2} t_{n/4} + (n/2)^{n/2}\right] + n^n \\ &= 2^{n + n/2} t_{n/4} + 2^n (n/2)^{n/2} + n^n \\ &= 2^{2n - n/2} t_{n/4} + 2^{n/2} n^{n/2} + n^n \\ &= 2^{2n - n/2} \left[2^{n/4} t_{n/8} + (n/4)^{n/4}\right] + 2^{n/2} n^{n/2} + n^n \\ &= 2^{2n - n/4} t_{n/8} + 2^{2n - n/2} \left[(n/4)^{n/4}\right] + 2^{n/2} n^{n/2} + n^n \\ &= 2^{2n - n/4} t_{n/8} + 2^n n^{n/4} + 2^{n/2} n^{n/2} + n^n \\ \end{split} $$ and you can iterate a couple more terms until yousee the pattern...

gt6989b
  • 54,422
0

Looks like a non-homogeneous difference equation.

\begin{equation} t(n)-2^{n} t(n / 2)=n^{n} \end{equation}