72.7k views
1 vote
Solve the following recurrence relation by expansion:

a. T(1) = 1, T(n) = 4 T(n/3) + n for n > 1.
b. T(1) = 1, T(n) = 2 T(n/2) + log n for n > 1.
c. T(1) = 1, T(n) = 2 T(n/4) + (n)1/2 for n > 1.

User SiH
by
7.6k points

1 Answer

5 votes

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

User Tatarize
by
8.3k points

No related questions found