0

i have below questions to solve. i tried this several times for one week. but i could not solve it. please can you help me to solve this.

recurence

enter image description here

amWhy
  • 209,954
etution lanka
  • 3

1 Answers1

0

$f(2^m) = 16 f(2^{m-1}) + 3.16^m = 16 (16 f(2^{m-2}) + 3.16^{m-1}) + 3.16^m = 16^2 f(2^{m-2}) + 2.3.16^m $

$= ... = 16^mf(2^0) + m.3.16^m = 16^m.3 + m.3.16^m = 3.16^m (m+1) = \Theta(m16^m) = \Theta((\log_2n)n^4)$

trang1618
  • 1,565