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 3^{i}(n/4^{i}). The iterations hits n = 1 when (n/4^{i}) = 1 or, equivalently, when i exceeds log_{4}n. 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 + ... + 3^{log4n
Ɵ (1)}

= 4n + o(n)

=
O(n)

Here, we concluded that 3^{log}_{4}^{n} = n^{log}_{4}^{3} and we have used the fact that log_{4}3 < 1 to conclude that

Ɵ n^{log}_{4}^{3} = o(n).

notes For Error Please Whatsapp @9300930012