CSC510-04 Analysis of Algorithms Recurrence Relations Jose Ortiz [email protected] Copyright Jose Ortiz Recurrence Relations Overview Motivation and Formal Definition The Back Substitution Method The Master Theorem Practice Problems 2 Recurrence Relations Motivation Defining sequences for recurrent functions using summations is not intuitive. Base cases cannot be represented in sequences Input size n repeats itself or decrease for each recurrent call. 3 Recurrence Relations Formal Definition Recurrent relation is an equation that defines itself Also known as recurrence equations At least one non-recursive output (base cases) One or more recursive cases (calls itself ) Once solved, they define the time complexity of the recurrence. 4 Recurrence Relations Techniques Two techniques to solve recurrent relations Back Substitution Recurrently substitutes T(n) until there is a clear sequence that defines a pattern. Master Theorem Provides an elegant solution in asymptotic terms for recurrence relations 5 Solving Recurrence Relations by The Back Substitution Method Recurrence Relations Back Substitution func greetings(n) { —> T(n) if (n<=0) -> T(0)= 0 return; print(“Hello”) —> 1 greetings(n-1) —> T(n-1) } 7 Solve by Back Substitution : . . Continue for k times . Assume (n-k) = 0 (base case). Thus, n=k. Then, T(n) = T(n 1) + 1 T(n) = [T(n 2) + 1] + 1 T(n) = T(n 2) + 2 T(n) = [T(n 3) + 1] + 2 T(n) = T(n 3) + 3 T(n) = T(n k) + k T(n) = T(0) + n→ T(n) = 0 + n > O(n) Recurrence Relations Back Substitution func greetings(n) { —> T(n) if (n<=0) -> T(0) = 1 return 1; print(“Hello”) —> 1 greetings(n-1) —> T(n-1) } 8 Solve by Back Substitution : . . Continue for k times . Assume (n-k) = 0 (base case). Thus, n=k. Then, T(n) = T(n 1) + 1 T(n) = [T(n 2) + 1] + 1 T(n) = T(n 2) + 2 T(n) = [T(n 3) + 1] + 2 T(n) = T(n 3) + 3 T(n) = T(n k) + k T(n) = T(0) + n→ T(n) = 1 + n > O(n) Recurrence Relations Back Substitution (loops) func greetings(n) { —> T(n) if (n<1) return; for(i=0; i n print(“Hello”) } greetings(n-1) —> T(n-1) } T(n) = T(n-1) + n 9 Solve by Back Substitution : . . Continue for k times . Assume (n-k) = 0 (base case). Thus, n=k. Then, T(n) = T(n 1) + n T(n) = [T(n 2) + (n 1)] + 1 T(n) = T(n 2) + (n 1) + 1 T(n) = [T(n 3) + (n 2)] + (n 1) + 1 T(n) = T(n 3) + (n 2) + (n 1) + 1 T(n) = T(n k) + (n (k 1)) + (n (k 2)) + . . . + (n 1) + n T(n) = T(n n) + (n (n 1)) + (n (n 2)) + . . . + (n 1) + n T(n) = T(1) + 1 + 2 + 3 + . . . + (n 1) + n T(n) = (n(n + 1) 2 ) = O(n2) Recurrence Relations Back Substitution (dividing) func greetings(n) { —> T(n) if (n<=1) return; print(“Hello”) —> 1 greetings(n/2) —> T(n/2) } T(n) = T(n/2) + 1 10 Solve by Back Substitution : . . Continue for k times . T(n) = T(n/2) + 1 T(n) = [T(n/22) + 1] + 1 T(n) = [T(n/22) + 2 T(n) = [T(n/23) + 1] + 2 T(n) = T(n/23) + 3 T(n) = T(n/2k) + k Assume (n/2k) = 1 (base case) then k = log n T(n) = T(1) + log n T(n) = 0 + log n T(n) = Θ(logn) Recurrence Relations Back Substitution (dividing) func greetings(n) { —> T(n) if (n<=1) return 1; for(i=0; i n print(“Hello”) } greetings(n/2) —> T(n/2) greetings(n/2) —> T(n/2) } T(n) = 2T(n/2) + n 11 Solve by Back Substitution : . . Continue for k times . T(n) = 2T(n/2) + n T(n) = 2[2T( n 22 ) + n 21 ] + n T(n) = 22T( n 22 ) + 2n T(n) = 22[2T( n 23 ) + n 22 ] + 2n T(n) = 23T( n 23 ) + 3n T(n) = 2kT(n/2k) + kn Assume T(n/2k) = T(1) (base case) then 2k = n; k = log n T(n) = nT(1) + nlogn T(n) = n + n log n = Θ(nlogn) Recurrence Relations Back Substitution Example 12 Assuming that , solve the following recurrence equation T(1) = 1 T(n) = 2T(n 2 ) + n3 T(n) = 2T(n 2 ) + n3 T(n) = 22T( n 22 ) + n 3 22 + n3 T(n) = 23T( n 23 ) + n 3 24 + n 3 22 + n3 After k steps . . . T(n) = 2kT( n 2k ) + n3( 1 40 + 1 41 + . . . + 1 4k 1 ) T(n) = 2kT(1) + n3( k 1 ∑ i=0 ( 1 4 )i) T(n) = n + 4n 3 3 (1 1 n2 ) T(n) = O(n3) Assume: T( n 2k ) = 1 2k = n k = log n Recurrence Relations Back Substitution Example 13 Assuming that , solve the following recurrence equation T(1) = 1 T(n) = 3T( n 4 ) + n T(n) = 3T(n 4 ) + n T(n) = 32T( n 42 ) + 3n 4 + n T(n) = 32T( n 42 ) + 3 2n 42 + 3n 4 + n After k steps . . . T(n) = 3kT( n 4k ) + n( 3 4 + 3 2 42 + 3 3 43 + . . . + 3 k 1 4k 1 ) T(n) = 3log4 nT(1) + n( k 1 ∑ i=1 ( 3 4 )i) T(n) = nlog4 3T(1) + 4n(1 n log4 3 n ) T(n) = O(n) Assume: T( n 4k ) = 1 4k = n k = log4 n Recurrence Relati
ons Back Substitution Example 14 Assuming that , solve the following recurrence equation . . T(0) = 1 T(n) = T(n 1) + logn T(n) = T(n 2) + log(n 1) + logn T(n) = T(n 3) + log(n 2) + log(n 1) + logn T(n) = T(n k) + log(n (k 1)) + log(n (k 2)) + . . . + log(1) T(n) = T(n k) + log(n!) T(n) = T(0) + nlogn T(n) = 1 + nlogn T(n) = O(nlogn) Note that log(n!) ≈ nlogn Assume: n k = 0 n = k T(0) = 1 Recurrence Equations Exam Review 15 1. 2. 3. 4. 5. T(n) = 7T( n 3 ) + n2 T(n) = 16T( n 4 ) + n2 T(n) = 7T( 9n 10 ) + n T(n) = 2T( n 2 ) + n log n T(n) = T(n 1) + logn Solving Recurrence Relation Using The Master Theorem Recurrence Relations The Master Theorem for conquering and dividing functions T(n) = aT( n b ) + f(n)); (1) logb a; (2) k a ≥ 1; b > 1; f(n) = Θ(nk logp n) Case 1 : if logb a > k then Θ(nlogb a) Case 2 : if logb a = k if p > 1 Θ(nk logp+1 n) if p = 1 Θ(nk log log n) if p < 1 Θ(nk) Case 3 : if logb a < k; if p ≥ 0 Θ(nk logp n) if p < 0 Θ(nk) 17 Example: a = 1 b = 2 p = 0 k= 0 Case 2 because And since p > -1 then T(n) = T(n 2 ) + 1 log2 1 = 0 Θ(n0 log0+1 n) = Θ(log n) Recurrence Relations The Master Theorem for conquering and dividing functions T(n) = aT( n b ) + f(n)); (1) logb a; (2) k a ≥ 1; b > 1; f(n) = Θ(nk logp n) Case 1 : if logb a > k then Θ(nlogb a) Case 2 : if logb a = k if p > 1 Θ(nk logp+1 n) if p = 1 Θ(nk log log n) if p < 1 Θ(nk) Case 3 : if logb a < k; if p ≥ 0 Θ(nk logp n) if p < 0 Θ(nk) 18 Example: a = 2 b = 2 p = 0 k= 0 Case 1 because T(n) = 2T(n 2 ) + 1 log2 2 > 0 Θ(n1) = Θ(n) Recurrence Relations The Master Theorem for conquering and dividing functions T(n) = aT( n b ) + f(n)); (1) logb a; (2) k a ≥ 1; b > 1; f(n) = Θ(nk logp n) Case 1 : if logb a > k then Θ(nlogb a) Case 2 : if logb a = k if p > 1 Θ(nk logp+1 n) if p = 1 Θ(nk log log n) if p < 1 Θ(nk) Case 3 : if logb a < k; if p ≥ 0 Θ(nk logp n) if p < 0 Θ(nk) 19 Example: a = 4 b = 2 p = 0 k=1 Case 1 because T(n) = 4T(n 2 ) + n log2 4 > 1 Θ(nlog2 4) = Θ(n2) Recurrence Relations The Master Theorem for conquering and dividing functions T(n) = aT( n b ) + f(n)); (1) logb a; (2) k a ≥ 1; b > 1; f(n) = Θ(nk logp n) Case 1 : if logb a > k then Θ(nlogb a) Case 2 : if logb a = k if p > 1 Θ(nk logp+1 n) if p = 1 Θ(nk log log n) if p < 1 Θ(nk) Case 3 : if logb a < k; if p ≥ 0 Θ(nk logp n) if p < 0 Θ(nk) 20 Example: a = 8 b = 2 p = 0 k=3 Case 2 because Then, since p>-1, T(n) = 8T(n 2 ) + n3 log2 8 = 3 Θ(n3 log0+1 n) = Θ(n3 log n) Recurrence Relations The Master Theorem for conquering and dividing functions T(n) = aT( n b ) + f(n)); (1) logb a; (2) k a ≥ 1; b > 1; f(n) = Θ(nk logp n) Case 1 : if logb a > k then Θ(nlogb a) Case 2 : if logb a = k if p > 1 Θ(nk logp+1 n) if p = 1 Θ(nk log log n) if p < 1 Θ(nk) Case 3 : if logb a < k; if p ≥ 0 Θ(nk logp n) if p < 0 Θ(nk) 21 Example: a = 7 b = 3 p = 0 k=2 Case 3 because Then, since p = 0, T(n) = 7T(n 3 ) + n2 log3 7 < 2 Θ(n2 log0 n) = Θ(n2) Recurrence Relations The Master Theorem for conquering and dividing functions T(n) = aT( n b ) + f(n)); (1) logb a; (2) k a ≥ 1; b > 1; f(n) = Θ(nk logp n) Case 1 : if logb a > k then Θ(nlogb a) Case 2 : if logb a = k if p > 1 Θ(nk logp+1 n) if p = 1 Θ(nk log log n) if p < 1 Θ(nk) Case 3 : if logb a < k; if p ≥ 0 Θ(nk logp n) if p < 0 Θ(nk) 22 Example: a = 2 b = 2 p = -1 k=1 Case 2 because Then, since p=-1, T(n) = 2T(n 2 ) + n log n → T(n) = 2T(n 2 ) + n log 1 n log2 2 = 1 Θ(n log log n) Recurrence Relations The Master Theorem for conquering and dividing functions T(n) = aT( n b ) + f(n)); (1) logb a; (2) k a ≥ 1; b > 1; f(n) = Θ(nk logp n) Case 1 : if logb a > k then Θ(nlogb a) Case 2 : if logb a = k if p > 1 Θ(nk logp+1 n) if p = 1 Θ(nk log log n) if p < 1 Θ(nk) Case 3 : if logb a < k; if p ≥ 0 Θ(nk logp n) if p < 0 Θ(nk) 23 Example: a = 7 b = 4 p = 0 k=0 Case 1 because T(n) = 7T(n 4 ) + 4n + 2 log4 7 > 0 Θ(nlog4 7) Recurrence Relations Exam Review 24 1. Assuming that , solve the following recurrence equation using the Back Substitution method 2. Check your solution using the master theorem T(1) = 0 T(n) = 8T(n 4 ) + n2 + 1