Asymptotic order of growth A way of comparing functions that ignores constant factors and small input sizes(because?) n O(g(n): class of functions f(n)that grow no faster than g(n) n o(g(n): class of functions f(n) that grow at same rate as g(n) n 2(g(n): class of functions f(n) that grow at least as fast as g( Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin "Intoducion to the Design Analysis of Algorithms, 2nd ed, Ch 2 2-10
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-10 Asymptotic order of growth A way of comparing functions that ignores constant factors and small input sizes (because?) O(g(n)): class of functions f(n) that grow no faster than g(n) Θ(g(n)): class of functions f(n) that grow at same rate as g(n) Ω(g(n)): class of functions f(n) that grow at least as fast as g(n)
Bi Ig-oh doesnt matter Figure 2.1 Big-oh notation: t(nEo(g(n)) Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin "Intoducfon to the Design Analysis of Algorithms, 2nd ed, Ch 2 2-11
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-11 Big-oh
Big-omega cg(n doesn t matter Fig. 2. 2 Big-omega notation: t(nEs(g(n) Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin "Intoducion to the Design Analysis of Algorithms, "2nd ed, Ch 2 2-12
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-12 Big-omega
Big-theta ig(n) cg doesn t matter Figure23 Big-theta notation:t(n)∈θ(g(n) Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin"Intoducion to the Design Analysis of Algorithms, " 2nd ed, Ch 2 2-13
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-13 Big-theta
Establishing order of growth using the definition Definition: f(n) is in O(g(n), denoted f(n) O(g(), if order of growth of f(n) s order of growth of g(n)(within constant multiple), i.e., there exist positive constant c and non-negative integer no such that f(m)≤cg(m) for every n≥ Examples: 口10 n is in o(2) 口5n+20 is in o(m) Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin "Intoducion to the Design Analysis of Algorithms, 2nd ed, Ch 2 2-14
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-14 Establishing order of growth using the definition Definition: f(n) is in O(g(n)), denoted f(n) O(g(n)), if order of growth of f(n) ≤ order of growth of g(n) (within constant multiple), i.e., there exist positive constant c and non-negative integer n0 such that f(n) ≤ c g(n) for every n ≥ n0 Examples: 10n is in O(n 2 ) 5n+20 is in O(n)