Page 1 Chapter 2 Computational Complexity Page 2 Chapter 2 Computational Complexity Computational Complexity ?Compares growth of two functions ?Independent of constant multipliers and lower-order effects ?Metrics ?“Big O” Notation O() ?“Big Omega” Notation ?() ?“Big Theta” Notation T() Page 3 Chapter 2 Computational Complexity Computational Complexity ?Compares growth of two functions ?Independent of constant multipliers and lower-order effects ?Metrics ?“Big O” Notation O() ?“Big Omega” Notation ?() ?“Big Theta” Notation T() Big “O” Notation ? f(n) =O(g(n)) ? If and only if there exist two constants c > 0 and n 0 > 0, such that f(n) = cg(n) for all n = n 0 ? iff ? c, n 0 > 0 s.t. ? n = n 0 : 0 = f(n) = cg(n) n 0 f(n) cg(n) f(n) is eventually upper- bounded by g(n) Page 4 Chapter 2 Computational Complexity Computational Complexity ?Compares growth of two functions ?Independent of constant multipliers and lower-order effects ?Metrics ?“Big O” Notation O() ?“Big Omega” Notation ?() ?“Big Theta” Notation T() Big “O” Notation ? f(n) =O(g(n)) ? If and only if there exist two constants c > 0 and n 0 > 0, such that f(n) = cg(n) for all n = n 0 ? iff ? c, n 0 > 0 s.t. ? n = n 0 : 0 = f(n) = cg(n) n 0 f(n) cg(n) f(n) is eventually upper- bounded by g(n) Big “Omega” Notation ? f(n) = ?(g(n)) ?iff ? c, n 0 > 0 s.t. ? n = n0 , 0 = cg(n) = f(n) f(n) cg(n) n 0 f(n) is eventually lower-bounded by g(n) Page 5 Chapter 2 Computational Complexity Computational Complexity ?Compares growth of two functions ?Independent of constant multipliers and lower-order effects ?Metrics ?“Big O” Notation O() ?“Big Omega” Notation ?() ?“Big Theta” Notation T() Big “O” Notation ? f(n) =O(g(n)) ? If and only if there exist two constants c > 0 and n 0 > 0, such that f(n) = cg(n) for all n = n 0 ? iff ? c, n 0 > 0 s.t. ? n = n 0 : 0 = f(n) = cg(n) n 0 f(n) cg(n) f(n) is eventually upper- bounded by g(n) Big “Omega” Notation ? f(n) = ?(g(n)) ?iff ? c, n 0 > 0 s.t. ? n = n0 , 0 = cg(n) = f(n) f(n) cg(n) n 0 f(n) is eventually lower-bounded by g(n) Big “Theta” Notation ? f(n) = T(g(n)) ? iff ? c 1 , c 2 , n 0 > 0 s.t. 0 = c 1 g(n) = f(n) = c 2 g(n), ? n >= n 0 f(n) c 1 g(n) n 0 c 2 g(n) f(n) has the same long-term rate of growth as g(n)Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!