Question? Leave a message!




Analysis of Divide and Conquer Algorithms

Analysis of Divide and Conquer Algorithms
Dr.JakeFinlay Profile Pic
Dr.JakeFinlay,Germany,Teacher
Published Date:22-07-2017
Website URL
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 / 23Plan 1 Review of Complexity Notions 2 Divide-and-Conquer Recurrences (Moreno Maza) Analysis of Divide and Conquer Algorithms CS3101 2 / 23Review of Complexity Notions Plan 1 Review of Complexity Notions 2 Divide-and-Conquer 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 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 / 23