AsymptoticsOutlineIntroduction (1)Introduction (2): Magnitude GraphIntroduction (3)Slide 6Big-O DefinitionBig-Omega DefinitionBig-Theta DefinitionAsymptotic Properties (1)Asymptotic Properties (2)Slide 12Asymptotic Proof TechniquesAsymptotic Proof Techniques: Example AAsymptotic Proof Techniques: Example B (1)Example B: ProofAsymptotic Proof Techniques: Example C (1)Example C: ProofAsymptotic Proof Techniques: Trick for polynomials of degree 2Slide 20Limit Method: MotivationLimit Method: The Process(Guillaume de) L’Hôpital RuleUseful Identities & DerivativesL’Hôpital Rule: Justification (1)L’Hôpital Rule: Justification (2)L’Hôpital Rule: Justification (3)Limit Method: Example 1Limit Method: Example 1—Proof ALimit Method: Example 1—Proof BLimit Method: Example 2 (1)Limit Method: Example 2 (2)Limit Method: Example 2 (3)Slide 34Limit PropertiesEfficiency Classes—Table 1, page 196ConclusionsSummaryAsymptoticsSection 3.2 of RosenSpring 2010CSCE 235 Introduction to Discrete StructuresCourse web-page: cse.unl.edu/~cse235Questions: [email protected] 235, Spring 20102Outline•Introduction•Asymptotic–Definitions (Big O, Omega, Theta), properties•Proof techniques–3 examples, trick for polynomials of degree 2, –Limit method (l’Hôpital Rule), 2 examples •Limit Properties•Efficiency classes•ConclusionsAsymptoticsCSCE 235, Spring 20103Introduction (1)•We are interested only in the Order of Growth of an algorithm’s complexity•How well does the algorithm perform as the size of the input grows: n •We have seen how to mathematically evaluate the cost functions of algorithms with respect to –their input size n and –their elementary operations•However, it suffices to simply measure a cost function’s asymptotic behaviorAsymptoticsCSCE 235, Spring 20104Introduction (2): Magnitude GraphAsymptoticsCSCE 235, Spring 20105Introduction (3)•In practice, specific hardware, implementation, languages, etc. greatly affect how the algorithm behave•Our goal is to study and analyze the behavior of algorithms in and of themselves, independently of such factors•For example–An algorithm that executes its elementary operation 10n times is better than one that executes it 0.005n2 times–Also, algorithms that have running time n2 and 2000n2 are considered asymptotically equivalentAsymptoticsCSCE 235, Spring 20106Outline•Introduction•Asymptotic–Definitions (Big-O, Omega, Theta), properties•Proof techniques•Limit Properties•Efficiency classes•ConclusionsAsymptoticsCSCE 235, Spring 20107Big-O Definition•Definition: Let f and g be two functions f,g:NR+. We say thatf(n) O(g(n))(read: f is Big-O of g) if there exists a constant c R+ and an noN such that for every integer n n0 we havef(n) cg(n)•Big-O is actually Omicron, but it suffices to write “O”•Intuition: f is asymptotically less than or equal to g•Big-O gives an asymptotic upper boundAsymptoticsCSCE 235, Spring 20108Big-Omega Definition•Definition: Let f and g be two functions f,g:NR+. We say thatf(n) (g(n))(read: f is Big-Omega of g) if there exists a constant c R+ and an noN such that for every integer n n0 we havef(n) cg(n)•Intuition: f is asymptotically greater than or equal to g•Big-Omega gives an asymptotic lower boundAsymptoticsCSCE 235, Spring 20109Big-Theta Definition•Definition: Let f and g be two functions f,g: NR+. We say thatf(n) (g(n))(read: f is Big-Omega of g) if there exists a constant c1, c2 R+ and an noN such that for every integer n n0 we havec1g(n) f(n) c2g(n)•Intuition: f is asymptotically equal to g•f is bounded above and below by g•Big-Theta gives an asymptotic equivalenceAsymptoticsCSCE 235, Spring 201010Asymptotic Properties (1)•Theorem: For f1(n) O(g1(n)) and f2(n) O(g2(n)), we havef1(n) + f2(n) O( max{g1(n), g2(n)} )•This property implies that we can ignore lower order terms. In particular, for any polynomial with degree k such as p(n)=ank + bnk-1 + cnk-2 + …, p(n) O(nk)More accurately, p(n) (nk)•In addition, this theorem gives us a justification for ignoring constant coefficients. That is for any function f(n) and a positive constant ccf(n) (f(n))AsymptoticsCSCE 235, Spring 201011Asymptotic Properties (2)•Some obvious properties also follow from the definitions•Corollary: For positive functions f(n) and g(n) the following hold:–f(n) (g(n)) f(n) O(g(n)) and f(n) (g(n))–f(n) O(g(n)) g(n) (f(n))The proof is obvious and left as an exerciseAsymptoticsCSCE 235, Spring 201012Outline•Introduction•Asymptotic–Definitions (big O, Omega, Theta), properties•Proof techniques–3 examples, trick for polynomials of degree 2, –Limit method (l’Hôpital Rule), 2 examples •Limit Properties•Efficiency classes•ConclusionsAsymptoticsCSCE 235, Spring 201013Asymptotic Proof Techniques•Proving an asymptotic relationship between two given function f(n) and g(n) can be done intuitively for most of the functions you will encounter; all polynomials for example•However, this does not suffice as a formal proof•To prove a relationship of the form f(n)(g(n)), where is , , or , can be done using the definitions, that is–Find a value for c (or c1 and c2)–Find a value for n0(But this is not the only way.)AsymptoticsCSCE 235, Spring 201014Asymptotic Proof Techniques: Example AExample: Let f(n)=21n2+n and g(n)=n3•Our intuition should tell us that f(n) O(g(n))•Simply using the definition confirms this: 21n2+n cn3holds for say c=3 and for all nn0=8 •So we found a pair c=3 and n0=8 that satisfy the conditions required by the definition QED•In fact, an infinite number of pairs can satisfy this equationAsymptoticsCSCE 235, Spring 201015Asymptotic Proof Techniques: Example B (1)•Example: Let f(n)=n2+n and g(n)=n3. Find a tight bound of the form f(n)(g(n))•Our intuition tells us that f(n)O(g(n))•Let’s prove it formallyAsymptoticsCSCE 235, Spring 201016Example B: Proof•If n1 it is clear that 1. n n3 and 2. n2 n3•Therefore, we have, as 1. and 2.:n2+n n3 + n3 = 2n3•Thus, for n0=1 and c=2, by the definition of Big-O we have that f(n)=n2+n O(g(n3))AsymptoticsCSCE 235, Spring 201017Asymptotic Proof Techniques: Example C (1)•Example: Let f(n)=n3+4n2 and g(n)=n2. Find a
View Full Document
Unlocking...