Recurrences CLRS 4 1 4 2 Last time we discussed divide and conquer algorithms Divide and Conquer To Solve P 1 Divide P into smaller problems P1 P2 P3 Pk 2 Conquer by solving the smaller subproblems recursively 3 Combine solutions to P1 P2 Pk into solution for P Analysis of divide and conquer algorithms and in general of recursive algorithms leads to recurrences Merge sort lead to the recurrence T n 2T n 2 n or rather T n 1 If n 1 T d n2 e T b n2 c n If n 1 but we will often cheat and just solve the simple formula equivalent to assuming that n 2k for some constant k and leaving out base case and constant in Methods for solving recurrences 1 Substitution method 2 Iteration method Recursion tree method Master method 1 Solving Recurrences with the Substitution Method Idea Make a guess for the form of the solution and prove by induction Can be used to prove both upper bounds O and lower bounds Let s solve T n 2T n 2 n using substitution Guess T n cn log n for some constant c that is T n O n log n Proof Base case we need to show that our guess holds for some base case not necessarily n 1 some small n is ok Ok since function constant for small constant n Assume holds for n 2 T n 2 c n2 log n2 Question Why not n 1 Prove that holds for n T n cn log n T n 2T n 2 n n n 2 c log n 2 2 n cn log n 2 cn log n cn log 2 n cn log n cn n So ok if c 1 Similarly it can be shown that T n n log n Exercise Similarly it can be shown that T n T b n2 c T d n2 e n is n lg n Exercise The hard part of the substitution method is often to make a good guess How do we make a good i e tight guess Unfortunately there s no recipe for this one Try iteratively O n3 n3 O n2 n2 and so on Try solving by iteration to get a feeling of the growth 2 Solving Recurrences with the Iteration Recursion tree Method In the iteration method we iteratively unfold the recurrence until we see the pattern The iteration method does not require making a good guess like the substitution method but it is often more involved than using induction Example Solve T n 8T n 2 n2 T 1 1 T n n2 8T n 2 n n n2 8 8T 2 2 2 2 2 n n n2 82 T 2 8 2 4 n 2 2 2 n 2n 8 T 2 2 n n 2 2 2 n 2n 8 8T 3 2 2 2 2 n2 n n2 2n2 83 T 3 82 2 2 4 n 2 2 2 2 3 n 2n 2 n 8 T 3 2 n2 2n2 22 n2 23 n2 24 n2 Recursion depth How long how many iterations it takes until the subproblem has constant size i times where 2ni 1 i log n What is the last term 8i T 1 8log n T n n2 2n2 22 n2 23 n2 24 n2 2log n 1 n2 8log n logX n 1 2k n2 8log n k 0 logX n 1 2 k 2 23 log n n k 0 Now Plog n 1 k 0 2k is a geometric sum so we have 23 log n 2log n 3 n3 Plog n 1 k 0 2k 2log n 1 n T n n2 n n3 n3 2 1 Recursion tree A different way to look at the iteration method is the recursion tree discussed in the book 4 2 we draw out the recursion tree with cost of single call in each node running time is sum of costs in all nodes if you are careful drawing the recursion tree and summing up the costs the recursion tree is a direct proof for the solution of the recurrence just like iteration and substitution Example T n 8T n 2 n2 T 1 1 n2 2 1 n2 3 T n n 2 2 T n 2 n 2 2 T n 2 T n 4 log n T n 4 n2 n2 n 2 2 8 n 2 2 2n2 n 2 2 n 4 2 82 n 4 2 22n2 n 4 2 log n 8 T 1 T 1 T 1 T 1 3 Matrix Multiplication Let X and Y x11 x21 X x31 xn1 be n n x12 x22 x32 xn2 matrices x1n x1n x1n xnn We want to compute Z X Y zij Pn k 1 Xik Ykj Naive method uses n2 n n3 operations Divide and conquer solution Z A B C D E F G H A E B G A F B H C E D G C F D H The above naturally leads to divide and conquer solution Divide X and Y into 8 sub matrices A B C and D Do 8 matrix multiplications recursively Compute Z by combining results doing 4 matrix additions Lets assume n 2c for some constant c and let A B C and D be n 2 n 2 matrices Running time of algorithm is T n 8T n 2 n2 T n n3 But we already discussed a simpler naive O n3 algorithm Can we do better 3 1 Strassen s Algorithm Strassen observed the following Z where A B C D E F G H S1 S2 S4 S6 S4 S5 S6 S7 S2 S3 S5 S7 S1 B D G H S2 A D E H S3 A C E F S4 A B H S5 A F H S6 D G E S7 C D E Lets test that S6 S7 is really C E D G S6 S7 D G E C D E DG DE CE DE DG CE This leads to a divide and conquer algorithm with running time T n 7T n 2 n2 We only need to perform 7 multiplications recursively Division Combination can still be performed in n2 time Lets solve the recurrence using the iteration method T n 7T n 2 n2 n n n2 7 7T 2 2 2 2 n 7 2 2 2 n 2 n 7 T 2 2 2 7 2 n n 2 n 2 n 72 7T 3 2 2 2 2 2 7 2 2 n 7 2 3 2 n 2 n 2 n 7 T 3 2 2 2 7 2 7 2 2 7 3 2 7 2 n 2 n 2 n 2 n 2 log n 1 n2 7log n 2 2 2 2 logX n 1 i 0 7 i 2 n 7log n 22 7 log n 1 7log n 22 7log n n2 2 log n 7log n 2 7log n n2 2 7log n n log n 7 n2 Now we have …
View Full Document
Unlocking...