Divide and conquer algorithm examples

design and analysis of algorithms divide and conquer ppt and Divide and conquer algorithm example problems
Dr.JakeFinlay Profile Pic
Dr.JakeFinlay,Germany,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
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 / 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 theN-to-R 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 / 23Divide-and-Conquer Recurrences Plan 1 Review of Complexity Notions 2 Divide-and-Conquer Recurrences (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 8 / 23Divide-and-Conquer Recurrences Divide-and-Conquer Algorithms Divide-and-conquer algorithms proceed as follows. Divide the input problem into sub-problems. Conquer on the sub-problems by solving them directly if they are small enough or proceed recursively. Combine the solutions of the sub-problems 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 divide-and-conquer 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 combine-part, a 1 is the number of recursively calls and n=b with b 1 is the size of a sub-problem. (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 9 / 23Divide-and-Conquer Recurrences Tree associated with a divide-and-conquer 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 sub-trees 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 / 23Divide-and-Conquer Recurrences Solving divide-and-conquer 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 / 23Divide-and-Conquer Recurrences Solving divide-and-conquer 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 … …Divide-and-Conquer 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 … …Divide-and-Conquer 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 … …Divide-and-Conquer 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 … …Divide-and-Conquer 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 / 23Divide-and-Conquer 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 / 23Divide-and-Conquer 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 / 23Divide-and-Conquer 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 / 23Divide-and-Conquer 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 / 23Divide-and-Conquer 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 / 23Divide-and-Conquer 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 / 23