0

Given this recurrence relation, T(n) = 2T(n/2)+T(n/4)+n^2, would I be able to utilize the Master Method to solve for the time complexity in the tightest bound?

I utilized the recursion tree method and got T(n) = Theta(n^2) as my answer, but I want to see if I can use the Master Method since that would be faster.

mathisfun1234
  • 49
  • Could you try to at least setup the master theorem for this problem? It’s about plugging things in. – Alex R. Oct 23 '21 at 02:20

1 Answers1

1

Let $n=2^k$ and $U(k)=T(n)=2U(k-1)+U(k-2)+4^k$

Characteristic equation is $x^2-2x-1=0$ of roots $1\pm\sqrt{2}$

Particular solution of the form $a\,4^k$ gives $a=\frac{16}7$

Therefore $U(k)=c_1(1+\sqrt{2})^k+c_2(1-\sqrt{2})^k+\frac{16}74^k$

Since $|1\pm\sqrt{2}|<4$ the dominant term is $4^k=n^2$ and you get $T(n)\sim\frac{16}7n^2$

zwim
  • 28,563