Theorem Ift1()∈ognm)andt2(m∈O(g2(m),then t1()+t2()∈o(mmxg1),g2(0) The analogous assertions are true for the 22-notation and⊙- notation o Implication: The algorithm's overallefficiency will be determined by e part with a larger order of growth le ffi ItS least encient par For example, 5n+ 3nlogn E o(n) Proof. There exist constants cl. c2, nI. n2 such that t1(m)≤c1xg1(m), for all n≥n (m)≤c2xg2(1), for all n≥ Define c3=CI+ c2 and n3=maxin, n2f. Ther ()+t2(m)≤c3xmx{g1(m,g2(m), for all n≥n3 Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin "Intoducion to the Design Analysis of Algorithms, 2nd ed, Ch 2 2-18Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-18 Theorem If t1 (n)  O(g1 (n)) and t2 (n)  O(g2 (n)), then t1 (n) + t2 (n)  O(max{g1 (n), g2 (n)}). • The analogous assertions are true for the -notation and -notation. Implication: The algorithm’s overall efficiency will be determined by the part with a larger order of growth, i.e., its least efficient part. • For example, 5n2 + 3nlogn  O(n2 ) Proof. There exist constants c1, c2, n1, n2 such that t1(n)  c1*g1(n), for all n  n1 t2(n)  c2*g2(n), for all n  n2 Define c3 = c1 + c2 and n3 = max{n1,n2}. Then t1(n) + t2(n)  c3*max{g1(n), g2(n)}, for all n  n3