UNC-Chapel Hill COMP 550 - symptotic Notation, Review of Functions & Summations (39 pages)

Previewing pages 1, 2, 3, 18, 19, 37, 38, 39 of 39 page document View the full content.
View Full Document

symptotic Notation, Review of Functions & Summations



Previewing pages 1, 2, 3, 18, 19, 37, 38, 39 of actual document.

View the full content.
View Full Document
View Full Document

symptotic Notation, Review of Functions & Summations

98 views


Pages:
39
School:
University of North Carolina at Chapel Hill
Course:
Comp 550 - Algorithms and Analysis
Unformatted text preview:

Asymptotic Asymptotic Notation Notation Review Review of of Functions Functions Summations Summations January 13 2019 Comp 122 Spring 2004 Asymptotic Complexity Running time of an algorithm as a function of input size n for large n Expressed using only the highest order term in the expression for the exact running time Instead of exact running time say n2 Describes behavior of function in the limit Written using Asymptotic Notation ymp 2 Comp 122 ymp 3 Asymptotic Notation O o Defined for functions over the natural numbers Ex f n n2 Describes how f n grows in comparison to n2 Define a set of functions in practice used to compare two function sizes The notations describe different rate of growth relations between the defining function and the defined set of functions Comp 122 notation For function g n we define g n big Theta of n as the set g n f n positive constants c1 c2 and n0 such that n n0 we have 0 c1g n f n c2g n Intuitively Set of all functions that have the same rate of growth as g n g n is an asymptotically tight bound for f n ymp 4 Comp 122 notation For function g n we define g n big Theta of n as the set g n f n positive constants c1 c2 and n0 such that n n0 we have 0 c1g n f n c2g n Technically f n g n Older usage f n g n I ll accept either f n and g n are nonnegative for large n ymp 5 Comp 122 ymp 6 Example g n f n positive constants c1 c2 and n0 such that n n0 0 c1g n f n c2g n 10n2 3n n2 What constants for n0 c1 and c2 will work Make c1 a little smaller than the leading coefficient and c2 a little bigger To compare orders of growth look at the leading term Exercise Prove that n2 2 3n n2 Comp 122 ymp 7 Example g n f n positive constants c1 c2 and n0 such that n n0 0 c1g n f n c2g n Is 3n3 n4 How about 22n 2n Comp 122 O notation For function g n we define O g n big O of n as the set O g n f n positive constants c and n0 such that n n0 we have 0 f n cg n Intuitively Set of all functions whose rate of growth is the same as or lower than that of g n g n is an asymptotic upper bound for f n f n g n f n O g n g n O g n ymp 8 Comp 122 Examples O g n f n positive constants c and n0 such that n n0 we have 0 f n cg n Any linear function an b is in O n2 How Show that 3n3 O n4 for appropriate c and n0 ymp 9 Comp 122 notation For function g n we define g n big Omega of n as the set g n f n positive constants c and n0 such that n n0 we have 0 cg n f n Intuitively Set of all functions whose rate of growth is the same as or higher than that of g n g n is an asymptotic lower bound for f n ymp 10 f n g n f n g n g n g n Comp 122 Example g n f n positive constants c and n0 such that n n0 we have 0 cg n f n n lg n Choose c and n0 ymp 11 Comp 122 ymp 12 Relations Between O Comp 122 Relations Between O Theorem Theorem For For any any two two functions functions g n g n and and f n f n f n f n g n g n iff iff f n f n O g n O g n and and f n f n g n g n I e g n O g n g n In practice asymptotically tight bounds are obtained from asymptotic upper and lower bounds ymp 13 Comp 122 ymp 14 Running Times Running time is O f n Worst case is O f n O f n bound on the worst case running time O f n bound on the running time of every input f n bound on the worst case running time f n bound on the running time of every input Running time is f n Best case is f n Can still say Worst case running time is f n Means worst case running time is given by some unspecified function g n f n Comp 122 ymp 15 Example Insertion sort takes n2 in the worst case so sorting as a problem is O n2 Why Any sort algorithm must look at each item so sorting is n In fact using e g merge sort sorting is n lg n in the worst case Later we will prove that we cannot hope that any comparison sort to do better in the worst case Comp 122 ymp 16 Asymptotic Notation in Equations Can use asymptotic notation in equations to replace expressions containing lower order terms For example 4n3 3n2 2n 1 4n3 3n2 n 4n3 n2 n3 How to interpret In equations f n always stands for an anonymous function g n f n In the example above n2 stands for 3n2 2n 1 Comp 122 o notation For a given function g n the set little o o g n f n c 0 n0 0 such that n n0 we have 0 f n cg n f n becomes insignificant relative to g n as n approaches infinity lim f n g n 0 n g n is an upper bound for f n that is not asymptotically tight Observe the difference in this definition from previous ones Why ymp 17 Comp 122 notation For a given function g n the set little omega g n f n c 0 n 0 such that n n0 we have 0 cg n f n 0 f n becomes arbitrarily large relative to g n as n approaches infinity lim f n g n n g n is a lower bound for f n that is not asymptotically tight ymp 18 Comp 122 ymp 19 Comparison of Functions f g a b f n O g n a b f n g n a b f n g n a b f n o g n a b f n g n a b Comp 122 ymp 20 Limits lim f n g n 0 f n g n n lim f n g n f n g n n 0 lim f n g n f n g n n 0 lim f n g n f n g n n lim f n g n f n g n n lim f n g n undefined can t say n Comp 122 ymp 21 Properties Transitivity f n g n g n h n f n h n f …


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view symptotic Notation, Review of Functions & Summations 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 symptotic Notation, Review of Functions & Summations 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?