CSE310 Lectures 03 04 Recurrences And the Master Method Guoliang Larry Xue Department of CSE Arizona State University http optimization asu edu xue Guoliang Xue asu edu Topics of this lecture Recurrences General form of recurrence 1st example block matrix multiplication 2nd example searching a sorted sequence The Master Method Case 1 f n O Case 2 f n Case 3 f n and Examples of using the Master Method 2 Guoliang Xue asu edu Recurrences General Form Very 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 Method 3 Guoliang Xue asu edu Recurrences First Example Let 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 B2j Therefore the time complexity of multiplying two Nby N matrices is T N such that T n 8T n 2 n2 a 8 b 2 f n n2 4 Guoliang Xue asu edu Recurrences Second Example Let T n be the time to search a sorted array of n elements using binary search Then we have T n T n 2 1 a 1 b 2 f n 1 5 Guoliang Xue asu edu The Master Method If f n O nlogba for some constant 0 then If f n nlogba then T n nlogba T 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 then T n f n 6 Guoliang Xue asu edu Example 1 T n 8T n 2 n2 a 8 b 2 f n n2 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 induction 7 Guoliang Xue asu edu Example 2 T n T n 2 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 this 8 Guoliang Xue asu edu More Examples Exercise 4 5 1 Exercise 4 5 2 Exercise 4 5 4 Exercise 4 5 5 9 Guoliang Xue asu edu It Does Not Work All the Times There 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 10 Guoliang Xue asu edu The Substitution Method Guess and Prove Example on Page 83 Example on Page 85 Pitfalls Page 86 Exercises 4 3 1 4 3 2 4 3 3 11 Guoliang Xue asu edu Summary Recurrences The Master Method 12 Guoliang Xue asu edu Readings and Exercises The 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 7 1 13 Guoliang Xue asu edu
View Full Document
Unlocking...