CSE 101 Class Notes Divide Conquer Integer Multiplication Master Theorem October 25 2006 Multiplication First Try Pn 1 P n 1 j 10 The We want the product of two numbers x i 0 xi 10i y j yj 0 grade school method is O n2 but we can do a faster version using divide andconquer As an example let x 1234 y 5678 Then 1234 5678 12 100 34 56 100 78 12 56 104 56 34 12 78 102 34 78 7066652 In general xy 10n xh yh 10n 2 xh yl xl yh xl yl or in pseudocode 1 2 3 4 5 6 7 8 9 10 11 12 13 14 mult x n 1 0 y n 1 0 if n 1 return lookup x y else xh x n 1 n 2 xl x n 2 0 yh y n 1 n 2 yl y n 2 0 a xh yh b xh yl c xl yh d xl yl bc add b c a append zeros a 2 floor n 2 bc append zeros bc floor n 2 return add a bc d Lines 5 6 take O n lines 7 10 take T n 2 each lines 11 13 take O n so the total running time is T n 4T n 2 O n 1 Running Time Depth 0 1 i log n TOTAL Subproblems 1 4 4i 4log n n2 Size n n 2 n 2i 1 Subprobem Time cn cn 2 cn 2i c Total time cn 4cn 2 2cn 4i cn 2i 2i cn cn2 Plog n i P i i 0 2 cn cn i 2 cn 2log n 1 1 n2 So this is no better than grade school multiplication Second Clever Try As it turns out we can do better than this by rearranging the work we do in lines 7 10 to reduce the number of subproblems to solve We need to compute the following expression xl yl 10n xl yh xh yl 10n 2 xh yh We can compute the three subterms using only three multiplications by recognizing that xl yh xh yl xl xh yl yh xl yl xh yh We already have to compute the last two terms so by computing xl xh yl yh we can find the 10n 2 term in one less recursive multiplication by subtracting out the last two Our table then becomes Depth Subproblems Size Subprobem Time Total time 0 1 n cn cn 1 3 n 2 cn 2 4cn 2 2cn i 3i n 2i cn 2i 3i cn 2i 1 5i cn log n 3log n nlog 3 1 c cnlog 3 TOTAL Plog n P i i i 0 1 5 cn cn i 1 5 log n 1 3log n 1 5 1 cn 2log n cn 1 5 1 3log n nlog 3 To get an idea of how much an improvement that is for n 10 17 for n 1000 and 309 for n 106 2 n2 nlog 3 n2 log 3 is 2 6 Master Theorem So far to find the running time of divide and conquer algorithms we have filled in a table like the one above However if we could fill in this table once for a generic divide and conquer algorithm we could simply read off the answer in the future Let s Depth Subproblems Size Subprobem Time Total time 0 1 n cnk cnk k 1 a n b c n b ac n b k i ai n bi c n bi k ai c n bi k logb n alogb n nlogb a 1 c cnlogb a The total time falls into one of three cases If the algorithm is top heavy i e a bk 1 then the top line of the table dominates and T n O nk If the algorithm is balanced i e a bk 1 then the total time is the sum of the times at each level or T n logb nO nk O nk logb n If the algorithm is bottom heavy i e a bk 1 then the table s height hence the number of base cases dominates and T n O nlogb a 3
View Full Document
Unlocking...