離散數(shù)學英文講義：3-2 The Growth of Functions

1、L o g oL o g o1 1Discrete MathematicsSouth China University of TechnologyDr. Han HuangL o g oL o g o2 2Section 3.2Chapter 3. Algorithms, Division and MatrixL o g oL o g oContentsIntroduction1Big-O2 Big-Theta3L o g oL o g oIntroductionL o g oL o g oOrders of Growth - MotivationvSuppose you are design

2、ing a web site to process user data (e.g., financial records).vSuppose database program A takes fA(n)=30n+8 microseconds to process any n records, while program B takes fB(n)=n2+1 microseconds to process the n records.vWhich program do you choose, knowing youll want to support millions of users?L o

3、g oL o g oVisualizing Orders of GrowthvOn a graph, asyou go to theright, the faster-growing func-tion always eventuallybecomes thelarger one. fA(n)=30n+8Increasing n fB(n)=n2+1Value of function L o g oL o g oConcept of order of growthvWe say fA(n)=30n+8 is (at most) order n, or O(n). It is, at most,

4、 roughly proportional to n.vfB(n)=n2+1 is order n2, or O(n2). It is (at most) roughly proportional to n2.vAny function whose exact (tightest) order is O(n2) is faster-growing than any O(n) function. Later we will introduce for expressing exact order.vFor large numbers of user records, the exactly or

5、der n2 function will always take more time.L o g oL o g oBig-O NotationL o g oL o g oDefinition: O(g), at most order gLet g be any function RR.vDefine “at most order g”, written O(g), to be: f:RR | c,k: xk: f(x) cg(x). “Beyond some point k, function f is at most a constant c times g (i.e., proportio

6、nal to g).”v“f is at most order g”, or “f is O(g)”, or “f=O(g)” all just mean that fO(g).vOften the phrase “at most” is omitted.L o g oL o g oPoints about the definitionvNote that f is O(g) so long as any values of c and k exist that satisfy the definition.vBut: The particular c, k, values that make

7、 the statement true are not unique: Any larger value of c and/or k will also work. vYou are not required to find the smallest c and k values that work. (Indeed, in some cases, there may be no smallest values!)However, you should prove that the values you choose do work.L o g oL o g o“Big-O” Proof Ex

8、amplesvShow that 30n+8 is O(n). Show c,k: nk: 30n+8 cn. Let c=31, k=8. Assume nk=8. Thencn = 31n = 30n + n 30n+8, so 30n+8 k: n2+1 cn2. Let c=2, k=1. Assume n1. Then cn2 = 2n2 = n2+n2 n2+1, or n2+10).vIt isnt evenless than 31neverywhere.vBut it is less than31n everywhere tothe right of n=8. nk=8 Big

9、-O example, graphicallyIncreasing n Value of function n30n+8cn =31n30n+8O(n)L o g oL o g oUseful Facts about Big OvBig O, as a relation, is transitive: fO(g) gO(h) fO(h)vO with constant multiples, roots, and logs. f (in (1) & constants a,bR, with b0, af, f 1-b, and (logb f)a are all O(f).vSums o

10、f functions:If gO(f) and hO(f), then g+hO(f).L o g oL o g oMore Big-O factsv c0, O(cf)=O(f+c)=O(f c)=O(f)vf1 O(g1) f2 O(g2) f1 f2 O(g1g2) f1+f2 O(g1+g2) = O(max(g1,g2) = O(g1) if g2 O(g1) (Very useful!)L o g oL o g oOrders of Growth - So FarvFor any g:RR, “at most order g”,O(g) f:RR | c,k xk |f(x)|

11、|cg(x)|. Often, one deals only with positive functions and can ignore absolute value symbols.v“f O(g)” often written “f is O(g)” or “f=O(g)”. The latter form is an instance of a more general convention.L o g oL o g oOrder-of-Growth Expressionsv“O(f)” when used as a term in an arithmetic expression m

12、eans: “some function f such that f O(f)”.vE.g.: “x2+O(x)” means “x2 plus some function that is O(x)”.vFormally, you can think of any such expression as denoting a set of functions: vx2+O(x) : g | f O(x): g(x)= x2+f(x)L o g oL o g oOrder of Growth EquationsvSuppose E1 and E2 are order-of-growth expre

13、ssions corresponding to the sets of functions S and T, respectively. vThen the “equation” E1=E2 really means f S, g T : f=gor simply S T.vExample: x2 + O(x) = O(x2) means f O(x): g O(x2): x2+f(x)=g(x)L o g oL o g oUseful Facts about Big Ov f,g & constants a,b R, with b 0, af = O(f); (e.g. 3x2 =

14、O(x2) f+O(f) = O(f); (e.g. x2+x = O(x2)vAlso, if f= (1) (at least order 1), then: |f|1-b = O(f); (e.g. x 1 = O(x) (logb |f|)a = O(f). (e.g. log x = O(x) g=O(fg) (e.g. x = O(x log x) fg O(g) (e.g. x log x O(x) a=O(f) (e.g. 3 = O(x)L o g oL o g oCasevLetv are real number.v v is 1110( ).nnnnf xa xaxa x

15、a110,.,nna aa a1110( ).nnnnf xa xaxa xa1110.nnnna xaxa xa1(1)110(.)nnnnnxaaxa xa x110(.)nnnxaaaa(1)x ( )nf xCx110.nnCaaaa1k ( )f x()nO xL o g oL o g oBig-Theta NotationL o g oL o g oDefinition: (g), exactly order gvIf f O(g) and g O(f), then we say “g and f are of the same order” or “f is (exactly)

16、order g” and write f(g).vAnother, equivalent definition: (g) f:RR | c1c2k0 xk: |c1g(x)| |f(x)| |c2g(x)| “Everywhere beyond some point k, f(x) lies in between two multiples of g(x).”L o g oL o g oRules for vMostly like rules for O( ), except:v f,g0 & constants a,b R, with b0, af (f), but Same as

17、with O. f (fg) unless g= (1) Unlike O.|f| 1-b (f), and Unlike with O. (logb |f|)c (f). Unlike with O.vThe functions in the latter two cases we say are strictly of lower order than (f).L o g oL o g o examplevDetermine whether:vQuick solution:)(2?1nini)()(2/ )(2/ ) 1(21nnnnnnniniL o g oL o g oOther Order-of-Growth Relationsv (g) = f | g O(f)“The functions that are at least order g.”vo(g) = f | c0 k xk : |f(x)| 0 k xk : |cg(x)| 1. Then the following are true:1 log log n log n logk n logk n n1/k n