Recurrence Relation for general form of equation

212 Views Asked by At

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

1

There are 1 best solutions below

2
On BEST ANSWER

$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)$