DOC PREVIEW
BU CS 333 - Asymptotic Growth Rate

This preview shows page 1-2-3-20-21-22-41-42-43 out of 43 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Asymptotic Growth RateFunction GrowthOutlineThe “sets” and their use – big OhThe “sets” and their use – OmegaThe “sets” and their use – Omega cont.The “sets” and their use - ThetaThe functionsAsymptotic Upper Bound: big OAsymptotic Upper Bound: On2 + 10 n  O(n2) Why?Does 5n+2 ÎO(n)?Does n2Î O(n)? No.O ( g (n) ) = { f (n )| there exist positive constant c and positive integer N such that 0 £ f( n) £ c  g (n ) for all n ³ N }Asymptotic Lower Bound, Omega: WAsymptotic Lower Bound: WIs 5n-20Î W (n)?W ( g ( n )) = { f (n) | there exist positive constant c and a positive integer N such that 0 £ c * g (n ) £ f ( n) for all n ³ N }Asymptotic Tight Bound: QAsymptotic Bound Theta: QMore on QSlide 22Slide 23Slide 24More QLimits can be used to determine OrderExample using limitsL’Hopital’s RuleSlide 29Slide 30Slide 31Another upper bound “little oh”: omain difference between O and oLower-order terms and constantsAsymptotic notation in equationsTransitivity:Reflexivity:Symmetry and Transpose symmetry:Analogy between asymptotic comparison of functions and comparison of real numbers.Not All Functions are ComparableSlide 41Is O(g(n)) = (g(n))  o(g(n))?General RulesCutler/Head Growth of Functions 1Asymptotic Growth Rate01/14/19 CS575 / Class 1 Growth of Functions 2Function Growth•The running time of an algorithm as input size approaches infinity is called the asymptotic running time•We study different notations for asymptotic efficiency.•In particular, we study tight bounds, upper bounds and lower bounds.Cutler/Head Growth of Functions 3Outline•Why do we need the different sets?•Definition of the sets O, Omega and Theta•Classifying examples:–Using the original definition–Using limits•General Properties•Little Oh•Additional propertiesCutler/Head Growth of Functions 4The “sets” and their use – big Oh•Big “oh” - asymptotic upper bound on the growth of an algorithm•When do we use Big Oh?1. Theory of NP-completeness2. To provide information on the maximum number of operations that an algorithm performs–Insertion sort is O(n2) in the worst case•This means that in the worst case it performs at most cn2 operations–Insertion sort is also O(n6) in the worst case since it also performs at most dn6 operationsCutler/Head Growth of Functions 5The “sets” and their use – OmegaOmega - asymptotic lower bound on the growth of an algorithm or a problem*When do we use Omega?1. To provide information on the minimum number of operations that an algorithm performs–Insertion sort is (n) in the best case•This means that in the best case its instruction count is at least cn, –It is (n2) in the worst case•This means that in the worst case its instruction count is at least cn2Cutler/Head Growth of Functions 6The “sets” and their use – Omega cont.2. To provide information on a class of algorithms that solve a problem –Sort algorithms based on comparison of keys are (nlgn) in the worst case•This means that all sort algorithms based only on comparison of keys have to do at least cnlgn operations–Any algorithm based only on comparison of keys to find the maximum of n elements is (n) in every case•This means that all algorithms based only on comparison of keys to find maximum have to do at least cn operationsCutler/Head Growth of Functions 7The “sets” and their use - Theta•Theta - asymptotic tight bound on the growth rate of an algorithm –Insertion sort is  (n2) in the worst and average cases•The means that in the worst case and average cases insertion sort performs cn2 operations–Binary search is  (lg n) in the worst and average cases•The means that in the worst case and average cases binary search performs clgn operations•Note: We want to classify an algorithm using Theta. –In Data Structures used Oh•Little “oh” - used to denote an upper bound that is not asymptotically tight. n is in o(n3). n is not in o(n)01/14/19 CS575 / Class 1 Growth of Functions 8The functions•Let f(n) and g(n) be asymptotically nonnegative functions whose domains are the set of natural numbers N={0,1,2,…}.•A function g(n) is asymptotically nonnegative, if g(n)0 for all nn0 where n0NCutler/Head Growth of Functions 9Asymptotic Upper Bound: big Of (n)c  g (n)f (n) = O ( g ( n ))N Why only for n  N ?What is the purpose of multiplying by c > 0?Graph shows thatfor all n  N,f(n)  c*g(n)Cutler/HeadGrowth of Functions 10Asymptotic Upper Bound: ODefinition: Let f (n) and g(n) be asymptotically non-negative functions. We say f (n) is in O ( g ( n )) if there is a real positive constant c and a positive Integer N such that for every n N 0  f (n) c  g (n ).Or using more mathematical notationO ( g (n) ) = { f (n )| there exist positive constant c and a positive integer N such that 0  f( n) c  g (n ) for all n N }Cutler/HeadGrowth of Functions 11n2 + 10 n O(n2) Why?02004006008001000120014000 10 20 30n2 + 10n2 n2take c = 2N = 102n2 > n2 + 10 n for all n>=10Cutler/HeadGrowth of Functions 12Does 5n+2 O(n)?Proof: From the definition of Big Oh, there must exist c>0 and integer N>0 such that 0  5n+2cn for all nN.Dividing both sides of the inequality by n>0 we get: 0  5+2/nc.2/n  2, 2/n>0 becomes smaller when n increasesThere are many choices here for c and N. If we choose N=1 then c  5+2/1= 7.If we choose c=6, then 0  5+2/n6. So N  2.In either case (we only need one!) we have a c>o and N>0 such that 0  5n+2cn for all n N. So the definition is satisfied and 5n+2 O(n)Cutler/HeadGrowth of Functions 13Does n2 O(n)? No. We will prove by contradiction that the definition cannot besatisfied. Assume that n2 O(n).From the definition of Big Oh, there must exist c>0 and integer N>0 such that 0  n2cn for all nN.Dividing the inequality by n>0 we get 0  n c for all nN.n  c cannot be true for any n >max{c,N }, contradicting our assumptionSo there is no constant c>0 such that nc is satisfied for all nN, and n2 O(n)Cutler/HeadGrowth of Functions 14O ( g (n) ) = { f (n )| there exist positive constant c and positive integer N such that 0  f( n) c  g (n ) for all n N }•1,000,000 n2  O(n2) why/why not?•(n - 1)n / 2  O(n2) why /why not?•n / 2  O(n2) why /why not?•lg (n2)  O( lg n ) why /why


View Full Document

BU CS 333 - Asymptotic Growth Rate

Download Asymptotic Growth Rate
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Asymptotic Growth Rate and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Asymptotic Growth Rate 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?