The recurrence relation t(1) =2, t(n) = 3t(n/4)+n has the solution t(n) equal to
Answers
Answered by
12
Answer:
As the recurrence equation is given:
= 3 (3t(n/4^2)+ n/4) +n
= 3^2t(n/4^2 ) + n(1+3/4)
= 3^2(3t(n/4^3) +n/4^2) + n(1+3/4)
= 3^3t(n/4^3 ) + n(1+3/4 + 3^2/4^2)
..............................
= 3^it(n/4^i) + n(1+3/4 + 3^2/4^2 + ........+3^(i-1)/4^(i-1))
we will stop at i = log4n, n/4^i = 1
Therefore,
t(n) = 3^ log4nt(1) +n . Σ(k-= to log4 n-1) (3/4)^k
<= 3log4n. Θ(1) + n Σ( k= 0 to infinity) (3/4)^k = Θn^log4(3)+4n = o(n)+4n
t(n) = O(n)
Answered by
0
Answer:(n^1.2logn)
Explanation:
Similar questions