1、Discrete Mathematical StructuresYang JCollege of Computer Science it may depend on your choice of kn Once you choose k and c, you must prove the truth of the implication (often by induction)8* College of Computer Science & Technology, BUPTPoints about the definitionn Note that f is O(g) so long as a
2、ny values of c and k exist that satisfy the definition.n But: The particular c, k, values that make the statement true are not unique: Any larger value of c and/or k will also work. n You are not required to find the smallest c and k values that work. (Indeed, in some cases, there may be no smallest
3、 values!)However, you should prove that the values you choose do work.9* College of Computer Science & Technology, BUPTlittle-o of gn In calculusn Ifn Thenn f is o(g) (called little-o of g)10* College of Computer Science & Technology, BUPTTheoremn If f is o(g) then f is O(g).n Proof: n by definition of limit as n goes to infinity, f(n)/g(n) gets arbitrarily small.n That is for any e 0, there must be an integer N such that when n N, | f(n)/g(n) | e .n Hence, choose c = e and k = N.n Q. E. D.
