CMSC 341ComplexityThe Goal of Asymptotic AnalysisGrowth FunctionsGrowth Functions (cont.)Slide 6A Graph of Growth FunctionsExpanded ScaleAsymptotic AnalysisAnalysis CasesCases ExampleDefinition of Big-OhBig-Oh ExampleT( N ) vs. N vs. 20NSimplifying AssumptionsExampleSlide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Space ComplexityConstants in BoundsSum in BoundsProducts in BoundsPolynomials in BoundsL’Hospital’s RulePolynomials of Logarithms in BoundsPolynomials vs Exponentials in BoundsLittle-Oh and Big-ThetaDetermining Relative Order of GrowthDetermining relative order of GrowthRelative Orders of Growth An ExerciseBig-Oh is not the whole storyAlgorithm AAlgorithm BTA( n ) vs. TB( n )A concrete exampleRelative Orders of Growth AnswersAmortized AnalysisAmortized Example – push_back( )Amortized Analysis ExampleAnalysisAnalysis, continuedCMSC 341Asymptotic Analysis8/3/07UMBC CMSC 341 AA2-color2ComplexityHow many resources will it take to solve a problem of a given size?timespaceExpressed as a function of problem size (beyond some minimum size)how do requirements grow as size grows?Problem sizenumber of elements to be handledsize of thing to be operated on8/3/07UMBC CMSC 341 AA2-color3The Goal of Asymptotic AnalysisHow to analyze the running time (aka computational complexity) of an algorithm in a theoretical model.Using a theoretical model allows us to ignore the effects of Which computer are we using?How good is our compiler at optimizationWe define the running time of an algorithm with input size n as T ( n ) and examine the rate of growth of T( n ) as n grows larger and larger and larger.8/3/07UMBC CMSC 341 AA2-color4Growth FunctionsConstantT(n) = cex: getting array element at known location any simple C++ statement (e.g. assignment)LinearT(n) = cn [+ possible lower order terms]ex: finding particular element in array of size n(i.e. sequential search)trying on all of your n shirts8/3/07UMBC CMSC 341 AA2-color5Growth Functions (cont.)QuadraticT(n) = cn2 [ + possible lower order terms]ex: sorting all the elements in an array (using bubble sort) trying all your n shirts with all your n tiesPolynomialT(n) = cnk [ + possible lower order terms]ex: finding the largest element of a k-dimensional arraylooking for maximum substrings in array8/3/07UMBC CMSC 341 AA2-color6Growth Functions (cont.)ExponentialT(n) = cn [+ possible lower order terms]ex: constructing all possible orders of array elementsTowers of Hanoi (2n)Recursively calculating nth Fibonacci number (2n)LogarithmicT(n) = lg n [ + possible lower order terms]ex: finding a particular array element (binary search)any algorithm that continually divides a problem in half8/3/07UMBC CMSC 341 AA2-color7A Graph of Growth Functions8/3/07UMBC CMSC 341 AA2-color8Expanded Scale8/3/07UMBC CMSC 341 AA2-color9Asymptotic AnalysisHow does the time (or space) requirement grow as the problem size grows really, really large?We are interested in “order of magnitude” growth rate.We are usually not concerned with constant multipliers. For instance, if the running time of an algorithm is proportional to (let’s suppose) the square of the number of input items, i.e. T(n) is c*n2, we won’t (usually) be concerned with the specific value of c.Lower order terms don’t matter.8/3/07UMBC CMSC 341 AA2-color10Analysis CasesWhat particular input (of given size) gives worst/best/average complexity?Best Case: If there is a permutation of the input data that minimizes the “run time efficiency”, then that minimum is the best case run time efficiencyWorst Case: If there is a permutation of the input data that maximizes the “run time efficiency”, then that maximum is the best case run time efficiencyAverage case is the “run time efficiency” over all possible inputs. Mileage example: how much gas does it take to go 20 miles?Worst case: all uphillBest case: all downhill, just coastAverage case: “average terrain8/3/07UMBC CMSC 341 AA2-color11Cases ExampleConsider sequential search on an unsorted array of length n, what is time complexity?Best case:Worst case:Average case:8/3/07UMBC CMSC 341 AA2-color12Definition of Big-OhT(n) = O(f(n)) (read “T( n ) is in Big-Oh of f( n )” )if and only if T(n)  cf(n) for some constants c, n0 and n  n0 This means that eventually (when n  n0 ), T( n ) is always less than or equal to c times f( n ).The growth rate of T(n) is less than or equal to that of f(n)Loosely speaking, f( n ) is an “upper bound” for T ( n )NOTE: if T(n) =O(f(n)), there are infinitely many pairs of c’s and n0’s that satisfy the relationship. We only need to find one such pair for the relationship to hold.8/3/07UMBC CMSC 341 AA2-color13Big-Oh ExampleSuppose we have an algorithm that reads N integers from a file and does something with each integer.The algorithm takes some constant amount of time for initialization (say 500 time units) and some constant amount of time to process each data element (say 10 time units). For this algorithm, we can say T( N ) = 500 + 10N.The following graph shows T( N ) plotted against N, the problem size and 20N.Note that the function N will never be larger than the function T( N ), no matter how large N gets. But there are constants c0 and n0 such that T( N ) <= c0N when N >= n0, namely c0 = 20 and n0 = 50.Therefore, we can say that T( N ) is in O( N ).8/3/07UMBC CMSC 341 AA2-color14T( N ) vs. N vs. 20N8/3/07UMBC CMSC 341 AA2-color15Simplifying Assumptions1. If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n))2. If f(n) = O(kg(n)) for any k > 0, then f(n) = O(g(n))3. If f1(n) = O(g1(n)) and f2(n) = O(g2(n)), then f1(n) + f2(n) = O(max (g1(n), g2(n)))4. If f1(n) = O(g1(n)) and f2(n) = O(g2(n)), then f1(n) * f2(n) = O(g1(n) * g2(n))8/3/07UMBC CMSC 341 AA2-color16ExampleCode:a = b;++sum;int y = Mystery( 42 );Complexity:8/3/07UMBC CMSC 341 AA2-color17ExampleCode:sum = 0;for (i = 1; i <= n; i++)sum += n;Complexity:8/3/07UMBC CMSC 341 AA2-color18ExampleCode:sum1 = 0;for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)sum1++;Complexity:8/3/07UMBC CMSC 341 AA2-color19ExampleCode:sum1 = 0;for (i = 1; i <= m; i++)for (j = 1; j <= n; j++)sum1++;Complexity:8/3/07UMBC CMSC 341 AA2-color20ExampleCode: sum2 = 0;for (i = 1 ; i <= n; i++)for (j = 1; j <= i; j++)sum2++;Complexity:8/3/07UMBC CMSC 341 AA2-color21ExampleCode:sum = 0;for (j