CSE310 Lectures 03-04: Recurrences And the Master MethodTopics of this lectureRecurrences-General FormRecurrences-First ExampleRecurrences-Second ExampleThe Master MethodExample 1: T(n) = 8T(n/2) + n2. a=8, b=2, f(n)=n2.Example 2: T(n) = T(n/2) + 1. a=1, b=2, f(n)=1.More Examples.It Does Not Work All the TimesThe Substitution MethodSummaryReadings and [email protected] Lectures 03-04:CSE310 Lectures 03-04:Recurrences And the Master MethodRecurrences And the Master MethodGuoliang (Larry) XueDepartment of CSEArizona State Universityhttp://optimization.asu.edu/[email protected] of this lectureTopics of this lectureRecurrencesGeneral form of recurrence1st example: block matrix multiplication2nd example: searching a sorted sequenceThe Master MethodCase 1: f(n) = O(…)Case 2: f(n) = (…)Case 3: f(n) = (…), and …Examples of using the Master [email protected] FormRecurrences-General FormVery often, the time complexity of an algorithm is given by a recurrence equation. We need to solve for it. The following is the general form:T(n) = a T(n/b) + f(n), a 1 and b > 1.How do we solve such recurrence?In this lecture, we will present a very general method, known as the Master [email protected] ExampleRecurrences-First ExampleLet A be an N-by-N matrix and B be an N-by-N matrix. We can use block multiplication to get the product of A with B.Assume that we partition A into A11, A12, A21, A22. We partition B into B11, B12, B21, B22. Let C be the product of A with B. Then Cij = Ai1 B1j + Ai2 B2jTherefore the time complexity of multiplying two N-by-N matrices is T(N) such thatT(n) = 8T(n/2) + n2. a=8, b=2, f(n)[email protected] ExampleRecurrences-Second ExampleLet T(n) be the time to search a sorted array of n elements, using binary search. Then we haveT(n) = T(n/2) + 1. a=1, b=2, f(n)[email protected] Master MethodThe Master MethodIf f(n) = O(nlogba-) for some constant > 0, thenT(n) = (nlogba) .If f(n) = (nlogba), thenT(n) = (nlogba lg n).If f(n) = (nlogba+) for some constant > 0, and a*f(n/b)c*f(n) for some constant c < 1 and all sufficiently large n, thenT(n) = (f(n)) [email protected] 1Example 1: T(n) = 8T(n/2) + n: T(n) = 8T(n/2) + n22. a=8, b=2, f(n)=n. a=8, b=2, f(n)=n22..This is the recurrence we got from the block matrix multiplication.lg28 = 3. So we have the first case (=0.5).Using the master method, we conclude that T(n) = (n3).We can also prove this using mathematical [email protected] 2Example 2: T(n) = T(n/2) + 1: T(n) = T(n/2) + 1. a=1, b=2, f(n)=1.. a=1, b=2, f(n)=1.This is the recurrence we got from binary searching of a sorted array.lg21 = 0. So we have the second case.Using the master method, we conclude that T(n) = (lg n).We can also prove this using mathematical induction, but it is not as easy as [email protected] Examples.More Examples.Exercise 4.5-1.Exercise 4.5-2.Exercise 4.5-4.Exercise [email protected] Does Not Work All the TimesIt Does Not Work All the TimesThere are some cases where the master method does not work.Consider the straight forward method for computing the n-th Fibonacci number.T(n) = T(n-1) + T(n-2) + 1.Well, the master method is not always useful…[email protected] Substitution MethodThe Substitution MethodGuess and Prove…Example on Page 83.Example on Page 85.Pitfalls, Page 86.Exercises 4.3-1, 4.3-2, [email protected]Recurrences.The Master [email protected] and ExercisesReadings and ExercisesThe materials covered in this lecture can be found in Section 4.5. Problem 4-1.Lecture 05 will be on Insertion sort and quick-sort. To preview, read Sections 2.1 and
View Full Document
Unlocking...