Question? Leave a message!




Analysis of Divide and Conquer Algorithms

Analysis of Divide and Conquer Algorithms
Analysis of Divide and Conquer Algorithms Marc Moreno Maza University of Western Ontario, London, Ontario (Canada) CS3101 (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 1 / 23Plan 1 Review of Complexity Notions 2 DivideandConquer Recurrences (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 2 / 23Review of Complexity Notions Plan 1 Review of Complexity Notions 2 DivideandConquer Recurrences (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 3 / 23Review of Complexity Notions Orders of magnitude Let f , g et h be functions fromN toR. We say that g(n) is in the order of magnitude of f (n) and we write f (n)2 (g(n)) if there exist two strictly positive constants c and c 1 2 such that for n big enough we have 0  c g(n)  f (n)  c g(n): (1) 1 2 We say that g(n) is an asymptotic upper bound of f (n) and we write f (n)2O(g(n)) if there exists a strictly positive constants c 2 such that for n big enough we have 0  f (n)  c g(n): (2) 2 We say that g(n) is an asymptotic lower bound of f (n) and we write f (n)2 (g(n)) if there exists a strictly positive constants c 1 such that for n big enough we have 0  c g(n)  f (n): (3) 1 (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 4 / 23Review of Complexity Notions Examples 1 2 2 With f (n) = n 3n and g(n) = n we have f (n)2 (g(n)): Indeed we 2 have 1 2 2 2 c n  n 3n  c n : (4) 1 2 2 1 1 for n 12 with c = and c = . 1 2 4 2 Assume that there exists a positive integer n such that f (n) 0 and 0 g(n) 0 for every n n . Then we have 0 max(f (n);g(n))2 (f (n) +g(n)): (5) Indeed we have 1 (f (n) +g(n))  max(f (n);g(n))  (f (n) +g(n)): (6) 2 Assume a and b are positive real constants. Then we have b b (n +a) 2 (n ): (7) Indeed for n a we have b b b 0  n  (n +a)  (2n) : (8) b Hence we can choose c = 1 and c = 2 . 1 2 (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 5 / 23Review of Complexity Notions Properties f (n)2 (g(n)) holds i f (n)2O(g(n)) and f (n)2 (g(n)) hold together. Each of the predicates f (n)2 (g(n)), f (n)2O(g(n)) and f (n)2 (g(n)) de ne a re exive and transitive binary relation among theNtoR functions. Moreover f (n)2 (g(n)) is symmetric. We have the following transposition formula f (n)2O(g(n)) () g(n)2 (f (n)): (9) In practice2 is replaced by = in each of the expressions f (n)2 (g(n)), f (n)2O(g(n)) and f (n)2 (g(n)). Hence, the following f (n) = h(n) + (g(n)) (10) means f (n)h(n)2 (g(n)): (11) (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 6 / 23Review of Complexity Notions Another example Let us give another fundamental example. Let p(n) be a (univariate) polynomial with degree d 0. Let a be its leading coecient and d assume a 0. Let k be an integer. Then we have d k (1) if k d then p(n)2O(n ), k (2) if k d then p(n)2 (n ), k (3) if k = d then p(n)2 (n ). Exercise: Prove the following k=n 2  k 2 (n ): (12) k=1 (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 7 / 23DivideandConquer Recurrences Plan 1 Review of Complexity Notions 2 DivideandConquer Recurrences (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 8 / 23DivideandConquer Recurrences DivideandConquer Algorithms Divideandconquer algorithms proceed as follows. Divide the input problem into subproblems. Conquer on the subproblems by solving them directly if they are small enough or proceed recursively. Combine the solutions of the subproblems to obtain the solution of the input problem. Equation satis ed by T (n). Assume that the size of the input problem increases with an integer n. Let T (n) be the time complexity of a divideandconquer algorithm to solve this problem. Then T (n) satis es an equation of the form: T (n) = aT (n=b) +f (n): (13) where f (n) is the cost of the combinepart, a 1 is the number of recursively calls and n=b with b 1 is the size of a subproblem. (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 9 / 23DivideandConquer Recurrences Tree associated with a divideandconquer recurrence Labeled tree associated with the equation. Assume n is a power of b, p say n = b : To solve the equation T (n) = aT (n=b) +f (n): we can associate a labeled treeA(n) to it as follows. (1) If n = 1, thenA(n) is reduced to a single leaf labeled T (1). (2) If n 1, then the root ofA(n) is labeled by f (n) andA(n) possesses a labeled subtrees all equal toA(n=b). The labeled treeA(n) associated with T (n) = aT (n=b) +f (n) has height p + 1. Moreover the sum of its labels is T (n). (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 10 / 23DivideandConquer Recurrences Solving divideandconquer recurrences (1/2) T(n) f(n) a … T( T(n/b /b)) T( T(n/b /b)) T( T(n/b /b)) T(n) f(n) a … f( f(n/b /b)) f( f(n/b /b)) f( f(n/b /b)) a f(n) 2 22 2 2 22 2 … 2 22 2 T( T( f( f(nn/b /b /b /b ))))T( T( f( f(nn/b /b /b /b)))) T( T( f( f(nn/b /b /b /b )))) a … T( T( f( f(nn/b /b /b /b)))) T( T( f( f(nn/b /b /b /b)))) T( T( f( f(nn/b /b /b /b)))) a 2 2 … 2 2 2 2 T( T(n/b /b )) T( T(n/b /b )) T(1) T( T(n/b /b )) (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 11 / 23DivideandConquer Recurrences Solving divideandconquer recurrences (2/2) f(n) f(n) a … f( f(n/b /b) ) f( f(n/b /b) ) af( f(n/b /b) ) f( f(n/b /b) ) h = log n b a 2 2 2 2 … 2 2 2 2 2 2 f( f(n/b /b ) ) f( f(n/b /b ) ) a f( f(n/b /b ) ) f( f(n/b /b ) ) log n b T(1) a T(1) log a b = Θ(n ) log log a a b IIDEA: C Compare n with ith f( f(n) ) . (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 12 / 23 … …DivideandConquer Recurrences log a b Master Theorem: case n  f (n) f(n) f(n) a … f(n/b f(n/b) ) f(n/b f(n/b) ) a af(n/b f(n/b) ) f(n/b f(n/b) ) log a h = log n b n≫ f(n) b a 2 2 2 2 … 2 2 2 2 2 2 GEOMETRICALLY GEOMETRICALLY f(n/b f(n/b ) ) f(n/b f(n/b ) ) a a f(n/b f(n/b ) ) f(n/b f(n/b ) ) INCREASING log log a a –εε Specifically Specifically, f(n) f(n) = O( O(n n b b ) ) for some constant ε 0 . log n b T(1) a T(1) log a b = Θ(n ) log g a b b T(n) T(n) = = ΘΘ( (n n ) ) (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 13 / 23 … …DivideandConquer Recurrences k log a b Master Theorem: case f (n)2 (n log n) f(n) f(n) a log log a a … b b n n≈≈ f(n) f(n) f(n/b f(n/b) ) f(n/b f(n/b) ) a af(n/b f(n/b) ) f(n/b f(n/b) ) h = log n b a ARITHMETICALLY 2 2 2 2 … 2 2 2 2 2 2 f(n/b f(n/b ) ) f(n/b f(n/b ) ) a a f(n/b f(n/b ) ) f(n/b f(n/b ) ) INCREASING log a k b Spy pecifically,, f() (n) = Θ( (n lg g n) ) for some constant k ≥ 0. log n b T(1) a T(1) log a b = Θ(n ) log a k+1 b b T(n) T(n) =ΘΘ(n (n lg lg n)) n)) (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 14 / 23 … …DivideandConquer Recurrences log a b Master Theorem: case where f (n) n f(n) f(n) log a b n≪ f(n) a … f(n/b f(n/b) ) f(n/b f(n/b) ) f(n/b f(n/b) ) a af(n/b f(n/b) ) GEOMETRICALLY GEOMETRICALLY h = log n b a DECREASING 2 2 … 2 2 2 2 2 2 2 2 f(n/b f(n/b ) ) f(n/b f(n/bSSi ) ) pecififica f(n/b f(n/b lllly, f( f() )n) ) = a a f(n/b f(n/b ) ) log a+ ε b Ω(n ) for some constant ε 0 . log n b T(1) a T(1) log a b = Θ(n ) T(n) = Θ(f(n)) and f(n) satisfies the regularity condition that a f(n/b) ≤ cf(n) for some constant c 1. (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 15 / 23 … …DivideandConquer Recurrences More examples Consider the relation: 2 T (n) = 2T (n=2) +n : (14) We obtain: 2 2 2 2 n n n n 2 T (n) = n + + + + + +nT (1): (15) p 2 4 8 2 Hence we have: 2 T (n)2 (n ): (16) Consider the relation: T (n) = 3T (n=3) +n: (17) We obtain: T (n)2 (log (n)n): (18) 3 (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 16 / 23DivideandConquer Recurrences Master Theorem when b = 2 Let a 0 be an integer and let f;T : NR be functions such that + (i) f (2n)  2f (n) and f (n)  n. p (ii) If n = 2 then T (n)  aT (n=2) +f (n): p Then for n = 2 we have (1) if a = 1 then T (n) (2 2=n)f (n) +T (1) 2 O(f (n)); (19) (2) if a = 2 then T (n) f (n) log (n) +T (1)n 2 O(log (n)f (n)); (20) 2 2 (3) if a 3 then   2 log (a)1 log (a) log (a)1 2 2 2 T (n) n 1 f (n)+T (1)n 2 O(f (n)n ): a 2 (21) (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 17 / 23DivideandConquer Recurrences Master Theorem when b = 2 Indeed p p1 p T (2 )  aT (2 ) +f (2 )   p2 p1 p  a aT (2 ) +f (2 ) +f (2 ) 2 p2 p1 p = a T (2 ) +af (2 ) +f (2 )   (22) 2 p3 p2 p1 p  a aT (2 ) +f (2 ) +af (2 ) +f (2 ) 3 p3 2 p2 p1 p = a T (2 ) +a f (2 ) +af (2 ) +f (2 ) j=p1 p j pj  a T (s1) + a f (2 ) j=0 (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 18 / 23DivideandConquer Recurrences Master Theorem when b = 2 Moreover p p1 f (2 )  2f (2 ) p 2 p2 f (2 )  2 f (2 ) (23) . . . . . . . . . p j pj f (2 )  2 f (2 ) Thus   j a j=p1 j pj p j=p1  a f (2 )  f (2 )  : (24) j=0 j=0 2 (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 19 / 23DivideandConquer Recurrences Master Theorem when b = 2 Hence   j a j=p1 p p p T (2 )  a T (1) +f (2 )  : (25) j=0 2 For a = 1 we obtain  j j=p1 p p 1 T (2 )  T (1) +f (2 )  j=0 2 1 1 p p 2 (26) = T (1) +f (2 ) 1 1 2 = T (1) +f (n) (2 2=n): For a = 2 we obtain p p p T (2 )  2 T (1) +f (2 )p (27) = nT (1) +f (n) log (n): 2 (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 20 / 23DivideandConquer Recurrences Master Theorem cheat sheet For a 1 and b 1, consider again the equation T (n) = aT (n=b) +f (n): (28) We have: log a" log a b b (9" 0) f (n)2 O(n ) =) T (n)2 (n ) (29) We have: log a k log a k+1 b b (9" 0)f (n)2 (n log n) =) T (n)2 (n log n) (30) We have: log a+" b (9" 0) f (n)2 (n ) =) T (n)2 (f (n)) (31) (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 21 / 23DivideandConquer Recurrences Master Theorem quizz T (n) = 4T (n=2) +n 2 T (n) = 4T (n=2) +n 3 T (n) = 4T (n=2) +n 2 T (n) = 4T (n=2) +n =logn (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 22 / 23DivideandConquer Recurrences Acknowledgements Charles E. Leiserson (MIT) for providing me with the sources of its lecture notes. (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 23 / 23