Asymptotic Notation, Review of Functions & SummationsAsymptotic ComplexityAsymptotic Notation-notationSlide 5ExampleSlide 7O-notationExamples -notationSlide 11Relations Between Q, O, WRelations Between Q, W, ORunning TimesSlide 15Asymptotic Notation in Equationso-notationw -notationComparison of FunctionsLimitsPropertiesSlide 22Common FunctionsMonotonicityExponentialsLogarithmsLogarithms and exponentials – BasesPolylogarithmsExerciseSummations – ReviewReview on SummationsSlide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Reading AssignmentJanuary 13, 2019 Comp 122, Spring 2004Asymptotic Notation,Review of Functions & SummationsAsymptotic Notation,Review of Functions & SummationsComp 122asymp - 2Asymptotic 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.Comp 122asymp - 3Asymptotic 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 122asymp - 4-notation(g(n)) = {f(n) :  positive constants c1, c2, and n0, such that n  n0,we have 0  c1g(n)  f(n)  c2g(n)}For function g(n), we define (g(n)), big-Theta of n, as the set:g(n) is an asymptotically tight bound for f(n).Intuitively: Set of all functions thathave the same rate of growth as g(n).Comp 122asymp - 5-notation(g(n)) = {f(n) :  positive constants c1, c2, and n0, such that n  n0,we have 0  c1g(n)  f(n)  c2g(n)}For function g(n), we define (g(n)), big-Theta of n, as the set: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.Comp 122asymp - 6Example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)(g(n)) = {f(n) :  positive constants c1, c2, and n0, such that n  n0, 0  c1g(n)  f(n)  c2g(n)}Comp 122asymp - 7ExampleIs 3n3  (n4) ??How about 22n (2n)??(g(n)) = {f(n) :  positive constants c1, c2, and n0, such that n  n0, 0  c1g(n)  f(n)  c2g(n)}Comp 122asymp - 8O-notationO(g(n)) = {f(n) :  positive constants c and n0, such that n  n0,we have 0  f(n)  cg(n) }For function g(n), we define O(g(n)), big-O of n, as the set:g(n) is an asymptotic upper bound for f(n).Intuitively: Set of all functions whose rate of growth is the same as or lower than that of g(n).f(n) = (g(n))  f(n) = O(g(n)).(g(n))  O(g(n)).Comp 122asymp - 9ExamplesAny linear function an + b is in O(n2). How?Show that 3n3=O(n4) for appropriate c and n0.O(g(n)) = {f(n) :  positive constants c and n0, such that n  n0, we have 0  f(n)  cg(n) }Comp 122asymp - 10 -notationg(n) is an asymptotic lower bound for f(n).Intuitively: Set of all functions whose rate of growth is the same as or higher than that of g(n).f(n) = (g(n))  f(n) = (g(n)).(g(n))  (g(n)).(g(n)) = {f(n) :  positive constants c and n0, such that n  n0,we have 0  cg(n)  f(n)}For function g(n), we define (g(n)), big-Omega of n, as the set:Comp 122asymp - 11Examplen = (lg n). Choose c and n0.(g(n)) = {f(n) :  positive constants c and n0, such that n  n0, we have 0  cg(n)  f(n)}Comp 122asymp - 12Relations Between , O, Comp 122asymp - 13Relations Between , , OI.e., (g(n)) = O(g(n))  (g(n))In practice, asymptotically tight bounds are obtained from asymptotic upper and lower bounds.Theorem : For any two functions g(n) and f(n), f(n) = (g(n)) iff f(n) = O(g(n)) and f(n) = (g(n)).Theorem : For any two functions g(n) and f(n), f(n) = (g(n)) iff f(n) = O(g(n)) and f(n) = (g(n)).Comp 122asymp - 14Running 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 122asymp - 15Example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 122asymp - 16Asymptotic 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 122asymp - 17o-notation 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?o(g(n)) = {f(n):  c > 0,  n0 > 0 such that  n  n0, we have 0  f(n) < cg(n)}.For a given function g(n), the set little-o:Comp 122asymp - 18(g(n)) = {f(n):  c > 0,  n0 > 0 such that  n  n0, we have 0  cg(n) < f(n)}. -notationf(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.For a given function g(n), the set little-omega:Comp 122asymp - 19Comparison of Functions f  g  a  bf (n) = O(g(n))  a  bf (n) = (g(n))  a  bf (n) = (g(n))  a = bf (n)