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 …