Using the master method in Section 4.5, you can show that the solution to the re
ID: 3669132 • Letter: U
Question
Using the master method in Section 4.5, you can show that the solution to the recurrence T(n) = 4T(n/3) + n is T(n) = (n^log 3 4). Show that a substitution proof with the assumption T(n) Cn^log 3 4 fails. Then show how to subtract off a lower-order term to make a substitution proof work. Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n less than= 2. Make your bounds as tight as possible, and justify your answers. T(n)=2T(n/2)+n^4 T(n)=T(7n/10)+n. T(n)=16T(/4)+n^2 T(n)=7T(n/3)+n^2 T(n)=7T(n/2)+n^2 T(n)=2T(n/4+square squareroot n T(n)=T(n-2)+n^2Explanation / Answer
T(n)4c(n/3)log34+n
cnlog34+n
We cannot proceed further with this.
Lets assume T(n)cnlog34-n . For all nn0,where c and n0 are positive constants.
T(n)4c(n/3)log34-4n+n
cnlog34-3n
cnlog34-n
Hence,our assumption is correct.
Case 1: f(n) is O(nlogba ). Since the leaves grow faster than f, asymptotically all of the work is done at the leaves, so T(n) is (nlogba).
Case 2: f(n) is (nlogba). The leaves grow at the same rate as f, so the same order of work is done at every level of the tree. The tree has O(log n) levels, times the work done on one level, yielding T(n) is (nlogba log n).
Case 3: f(n) is (nlogba + ). In this case f grows faster than the number of leaves, which means that asymptotically the total amount of work is dominated by the work done at the root node. For the upper bound, we also need an extra smoothness condition on f in this case, namely that af(n/b) cf(n) for some constant c < 1 and large n. In this case T(n) is (f(n)).
We need to check af( n/ b) cf(n) for some c<1and n large enough.
af (n/ b) = 2 (n/ 2) 4 = 1/ 8 n 4 = 1 /8 f(n) and case 3 applies.
So,we can conclude T(n) = (n 4 ) .
b.T(n)=T(7n/10)+n . T(n) = (n).In terms of master theorem,
a=1,b=10/7 so, logba=log10/71=0. f(n) = n = n logba+1 This looks like case 3.
We need to check af( n/ b) cf(n) for some c<1and n large enough
af (n/ b) = 1(7n/10)1 =7/10n=7/10f(n)and case 3 applies
So,we can conclude T(n) = (n ) .
c.T(n)= 16T (n/4) + n2; T(n) = ( n2 lg n); In terms of master theorem
So,we can conclude T(n) = ( n 2 lg n)
d. T (n) = 7T (n/3) + n2; T(n) = ( n2 lg n); In terms of master theorem
a = 7, b = 3; so, 1 < logb a = log3 7 <2; f(n) = n 2 = n logba+ for some >0;
This is case 3. We need to check af( n/ b) cf(n). for some c<1and n large enough.
In fact af( n/ b) = 7 (n /3)2 = 7/9n 2 = 7/ 9 f(n).and case 3 applies.
conclude T(n) = ( n2 lg n)
e. T(n)= 7T (n/2)+n2; T(n) = (n log27) In terms of master theorem
a = 7, b = 2; so, 2 < logb a = log 27 < 3. f(n) = n2= n logba;This is case 1.
Conclude T(n) = (n log27 )
f. T (n) = 2T (n/4) + n; T(n) = ( n lg n) in terms of master theorem.
a = 2, b = 4 so, log b a= = log 42= ½. f(n) = n (1/ 2 )= n logba;This is case 2
conclude T(n) = ( n lg n)
g. T(n) = T(n2)+n2; T(n) = (n3) The master theorem doesn’t apply.
A recursion tree or unwrapping the recurrence relation allows one to conclude
T(n) = T (n 2k) + n 2 + (n 2)2 + . . .(n 2 (k 1))2
I took the reference.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.