Asymptotics Section 3 2 of Rosen Spring 2010 CSCE 235 Introduction to Discrete Structures Course web page cse unl edu cse235 Questions cse235 cse unl edu Outline 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 Conclusions CSCE 235 Spring 2010 Asymptotics 2 Introduction 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 behavior CSCE 235 Spring 2010 Asymptotics 3 Introduction 2 Magnitude Graph CSCE 235 Spring 2010 Asymptotics 4 Introduction 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 equivalent CSCE 235 Spring 2010 Asymptotics 5 Outline Introduction Asymptotic Definitions Big O Omega Theta properties Proof techniques Limit Properties Efficiency classes Conclusions CSCE 235 Spring 2010 Asymptotics 6 Big O Definition Definition Let f and g be two functions f g N R We say that f n O g n read f is Big O of g if there exists a constant c R and an no N such that for every integer n n0 we have f 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 bound CSCE 235 Spring 2010 Asymptotics 7 Big Omega Definition Definition Let f and g be two functions f g N R We say that f n g n read f is Big Omega of g if there exists a constant c R and an no N such that for every integer n n0 we have f n cg n Intuition f is asymptotically greater than or equal to g Big Omega gives an asymptotic lower bound CSCE 235 Spring 2010 Asymptotics 8 Big Theta Definition Definition Let f and g be two functions f g N R We say that f n g n read f is Big Omega of g if there exists a constant c1 c2 R and an no N such that for every integer n n0 we have c1g 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 equivalence CSCE 235 Spring 2010 Asymptotics 9 Asymptotic Properties 1 Theorem For f1 n O g1 n and f2 n O g2 n we have f1 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 c cf n f n CSCE 235 Spring 2010 Asymptotics 10 Asymptotic 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 exercise CSCE 235 Spring 2010 Asymptotics 11 Outline 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 Conclusions CSCE 235 Spring 2010 Asymptotics 12 Asymptotic 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 CSCE 235 Spring 2010 Asymptotics 13 Asymptotic Proof Techniques Example A Example 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 cn3 holds for say c 3 and for all n n0 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 equation CSCE 235 Spring 2010 Asymptotics 14 Asymptotic 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 formally CSCE 235 Spring 2010 Asymptotics 15 Example B Proof If n 1 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 CSCE 235 Spring 2010 Asymptotics 16 Asymptotic Proof Techniques Example C 1 Example Let f n n3 4n2 and g n n2 Find a tight bound of the form f n g n Here 0ur intuition tells us that f n g n Let s prove it formally CSCE 235 Spring 2010 Asymptotics 17 Example C Proof For n 1 we have n2 n3 For n 0 we have n3 n3 4n2 Thus n 1 we have n2 n3 n3 4n2 Thus by the definition of Big for n0 1 and c 1 we have that f n n3 4n2 g n2 CSCE 235 Spring 2010 Asymptotics 18 Asymptotic Proof Techniques Trick for polynomials of degree 2 If you have a polynomial of degree 2 such as an2 bn c you can prove that it is n2 using the following values 1 c1 a 4 2 c2 7a 4 3 n0 2 max b a sqrt c a CSCE 235 Spring 2010 Asymptotics 19 Outline 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 Conclusions CSCE 235 Spring 2010 Asymptotics 20 Limit Method Motivation Now try this one f n n50 12n3log4n 1243n12 245n6logn 12log3n logn g n 12 n50 24 log14 n43 logn n5 12 Using the formal definitions can be very tedious especially one has very complex functions It is …
View Full Document
Unlocking...