Consider the recurrence relation T(n) = 27(n/2) + n log n with n = 2^k and T(1)
ID: 3883532 • Letter: C
Question
Consider the recurrence relation T(n) = 27(n/2) + n log n with n = 2^k and T(1) = 1. Prove by induction that T(n) = circleminus (n log^2 n). Consider the recurrence relation T(n) = T(n/2) + T(n/4) + 2n with n = 4^k and T(1) = 1. Prove by induction that T(n) = circleminus (n). Use the Master Theorem to determine the solutions to the following recurrences. Explain for each what case applies. T(n) = 5T(n/5) + 12n, n = 5^k, T(1) = 0 T(n) = 2T(n/4) + 4n^0.6, n = 4^k, T(1) = 0 T(n) = 3T(n/3) + squareroot n, n = 3^k, T(1) = 0Explanation / Answer
(iii) Using Masters Theorem
T(n) = 5T(n/5) + 12n , T(1) = 0
=> Lets use Masters theorem and see if its of the form T(n) = aT(n/b) + f(n)
a = 5, b = 5 and f(n) = O(n)
That means nlogb a = nlog5 5 = n1 = n
We can see that f(n) = n = nlogb a
This falls in Case 2 of Masters theorem , that means T(n) = O( nlogb a log n)
=> T(n) = O( nlog n)
b) T(n) = 2T(n/4) + 4n0.6 , T(1) = 0
=> Lets use Masters theorem and see if its of the form T(n) = aT(n/b) + f(n)
a = 2, b = 4 and f(n) = O(n0.6)
That means nlogb a = nlog4 2 = n0.5
We can see that f(n) = n0.6 >= nlogb a
This falls in Case 3 of Masters theorem , that means T(n) = ( f(n))
=> T(n) = O( n0.6 )
c) T(n) = 3T(n/3) + n0.5 , T(1) = 0
=> Lets use Masters theorem and see if its of the form T(n) = aT(n/b) + f(n)
a = 3, b = 3 and f(n) = O(n0.5)
That means nlogb a = nlog3 3 = n1
We can see that f(n) = n0.5 <= nlogb a
This falls in Case 1 of Masters theorem , that means T(n) = O( g(n))
=> T(n) = O( n)
Thanks, let me know if there is any concern.