PowerPoint PresentationSlide 2Slide 3Slide 4Slide 5Slide 6Growth of FunctionsSlide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 163.3 Complexity of Algorithm•The number of comparisons in linear search is f(n)=2n+1 for a list of n elements.•For bubble sort, it is g(n)= (n-1) + (n-2) …. + 2 +1 = (n-1) n / 2 for a list of n elements. So if list A is twice as long as list B, it will take four times longer to process A than BHere, we want to know the behavior of f (n), g(n) when n is large … (n=100,000 or more). That is the growth of the functions.n2n10n+1For sufficiently large values of n, n2 will always be larger than any linear function.n2n10n+1Compared with n2, all linear (degree-1) polynomials have the same growth pattern for large n values.n2n0.5n2+1n30.5n3+n2+1n2n40.5n4+n3+1n3Growth of Functions•Polynomials of a given degree have similar growth pattern when compared with polynomials of different degrees.•We need a language to describe the various growth patterns of
View Full Document