Analysis & Design of Algorithms

Q.9: Solve the recurrence relation: T(n) = 3 (n/4) + n

Answer:
Given
T(n) = 3 (n/4) + n

But the recurrence relation should be

T(n) = 3T(n/4) + n We iterate is as follows -

T(n) = n + 3T(n/4)

= n + 3(n/4 + 3T(n/16)) = n + 3(n/4 + 3(n/16) + 3T(n/64))

= n + 3(n/4) + 9(n/16) + 27T(n/64)

where ((n/4)/4) = (n/16) and ((n/16)/4) = (n/64).

The ith term in the series is 3i(n/4i). The iterations hits n = 1 when (n/4i) = 1 or, equivalently, when i exceeds log4n. By continuing the iteration until this point, we discover that the summation contains a decreasing geometric series

T(n) <= n + 3n/4 + 9n/16 + 27n/64 + ... + 3log4n Ɵ   (1)

 
T(n) = 3 (n/4) + n
= 4n + o(n)
= O(n)

Here, we concluded that 3log4n = nlog43 and we have used the fact that log43 < 1 to conclude that
Ɵ  nlog43 = o(n).


notes For Error Please Whatsapp @9300930012