Answer:
a. We have T(n) = 4 T(n/3) + n. Expanding this recurrence relation, we get:
T(n) = 4 T(n/3) + n
= 4 [4 T(n/9) + n/3] + n (substituting n/3 for n/3)
= 4^2 T(n/9) + 4n/3 + n
= 4^2 [4 T(n/27) + n/9] + 4n/3 + n
= 4^3 T(n/27) + 4n/3 + n/3 + n
= 4^3 T(n/27) + 5n/3
Continuing this process, we can express T(n) as:
T(n) = 4^k T(n/3^k) + (4^0 + 4^1 + ... + 4^{k-1}) n/3^{k-1}
The value of k we want to find is the one such that n/3^k = 1, or equivalently, 3^k = n. Taking the logarithm base 3 on both sides, we get k = log_3(n). Substituting this value into the expression above, we obtain:
T(n) = 4^{log_3(n)} T(1) + (4^0 + 4^1 + ... + 4^{log_3(n)-1}) n/3^{log_3(n)}
= n^(log_3(4)) + (4^0 + 4^1 + ... + 4^{log_3(n)-1}) n/3^{log_3(n)}
b. We have T(n) = 2 T(n/2) + log n. Expanding this recurrence relation, we get:
T(n) = 2 T(n/2) + log n
= 2 [2 T(n/4) + log(n/2)] + log n (substituting n/2 for n/2)
= 2^2 T(n/4) + 2 log(n/2) + log n
= 2^2 [2 T(n/8) + log(n/4)] + 2 log(n/2) + log n
= 2^3 T(n/8) + 3 log(n/2) + log n
= 2^3 [2 T(n/16) + log(n/8)] + 3 log(n/2) + log n
= 2^4 T(n/16) + 4 log(n/2) + log n
...
Continuing this process, we can express T(n) as:
T(n) = 2^k T(n/2^k) + (k log(n/2))
The value of k we want to find is the one such that n/2^k = 1, or equivalently, 2^k = n. Taking the logarithm base 2 on both sides, we get k = log_2(n). Substituting this value into the expression above, we obtain:
T(n) = 2^{log_2(n)} T(1) + (log_2(n)) log(n/2)
= n + (log_2(n)) log(n/2)
C. To solve the recurrence relation T(n) = 2 T(n/4) + (n)1/2, we use the expansion method:
T(n) = 2 T(n/4) + (n)1/2
= 2 [2 T(n/16) + (n/4)1/2] + (n)1/2
= 4 T(n/16) + 2(n/4)1/2 + (n)1/2
= 4 [2 T(n/64) + (n/16)1/2] + 2(n/4)1/2 + (n)1/2
= 8 T(n/64) + 4(n/16)1/2 + 2(n/4)1/2 + (n)1/2
= 8 [2 T(n/256) + (n/64)1/2] + 4(n/16)1/2 + 2(n/4)1/2 + (n)1/2
= 16 T(n/256) + 8(n/64)1/2 + 4(n/16)1/2 + 2(n/4)1/2 + (n)1/2
= ...
= n1/2 + 2(n/4)1/2 + 4(n/16)1/2 + ... + 2k(n/4k)1/2 + ... + 8(n/n1/2)1/2
We can see that the recursion stops when n/4k = 1, or k = log4 n. So we have:
T(n) = n1/2 + 2(n/4)1/2 + 4(n/16)1/2 + ... + 2^(log4 n)(n/4^(log4 n))1/2 + ... + 8(n/n1/2)1/2
= n1/2 * [1 + (1/2)^(1/2) + (1/4)^(1/2) + ... + (1/4^(log4 n))^(1/2)] + O(1)
= n1/2 * [1 + (1/2)^(1/2) + (1/4)^(1/2) + ... + (1/n)^(1/2)] + O(1)
Thus, the solution to the recurrence relation T(n) = 2 T(n/4) + (n)1/2 is T(n) = Θ(n1/2 log n).