Algorithmic Complexity 3OverviewCritical Section Example 7Recursive AlgorithmsRecursive Algorithm ExampleRecurrence RelationsSlide 7Solving Recurrence EquationsExample Recurrence SolutionsAsymptotic Complexity CategoriesComplexity Category ExampleSlide 12Calculating Asymptotic ComplexityComplexity ExamplesSlide 15Slide 16Slide 17Comparing ComplexityComplexity Comparison ExamplesL’Hopital’s RuleUsing L’Hopital’s RuleAdditional Complexity Measures2D Matrix Multiplication ExampleAdditional Complexity CategoriesNP Time AlgorithmSlide 26P = NP?Algorithmic Complexity SummaryAlgorithmic Complexity 3Fawzi EmadChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkOverviewRecurrence relationsComplexity categoriesComparing complexityTypes of complexity analysisCritical Section Example 7Code (for input size n)1. DoWork (int n)2. if (n == 1)3. A4. else5. DoWork(n/2)6. DoWork(n/2)Code executionA 1 timesDoWork(n/2) 2 timesTime(1) 1 Time(n) = 2 Time(n/2) + 1critical sectionsRecursive Algorithms DefinitionAn algorithm that calls itselfComponents of a recursive algorithm1. Base casesComputation with no recursion2. Recursive casesRecursive callsCombining recursive resultsRecursive Algorithm ExampleCode (for input size n)1. DoWork (int n)2. if (n == 1)3. A4. else5. DoWork(n/2)6. DoWork(n/2)recursive casesbase caseRecurrence RelationsDefinitionValue of a function at a point is given in terms of its value at other pointsExamplesT(n) = T(n-1) + k T(n) = T(n-1) + nT(n) = T(n-1) + T(n-2)T(n) = T(n/2) + kT(n) = 2 T(n/2) + kRecurrence RelationsBase caseValue of function at some specified pointsAlso called boundary values / boundary conditionsBase case exampleT(1) = 0T(1) = 1T(2) = 1T(2) = kSolving Recurrence EquationsBack substitution (iteration method)Iteratively substitute recurrence into formulaExampleT(1) = 5T(n) = T(n-1) + 1 = ( T(n-2) + 1 ) + 1= ( ( T(n-3) + 1 ) + 1 ) + 1= ( ( ( T(n-4) + 1 ) + 1 ) + 1 ) + 1= …= (…( T(1) + 1 ) + … ) + 1= (…( 5 + 1 ) + … ) + 1= n + 4Example Recurrence SolutionsExamplesT(n) = T(n-1) + k O(n)T(n) = T(n-1) + n O(n2)T(n) = T(n-1) + T(n-2) O(n!)T(n) = T(n/2) + k O(log(n))T(n) = 2 T(n/2) + k O(n)T(n) = 2 T(n-1) + k O(2n)Many additional issues, solution methodsTake CMSC 351 – Introduction to AlgorithmsAsymptotic Complexity Categories Complexity Name ExampleO(1) Constant Array accessO(log(n)) Logarithmic Binary searchO(n) Linear Largest elementO(n log(n)) N log N Optimal sortO(n2) Quadratic 2D Matrix additionO(n3) Cubic 2D Matrix multiplyO(nk) Polynomial Linear programmingO(kn) Exponential Integer programmingFrom smallest to largest For size n, constant k > 1Complexity Category Example0501001502002503001 2 3 4 5 6 7Problem Size# of Solution Steps2^nn^2nlog(n)nlog(n)Complexity Category Example11010010001 2 3 4 5 6 7Problem Size# of Solution Steps2^nn^2nlog(n)nlog(n)Calculating Asymptotic ComplexityAs n increasesHighest complexity term dominatesCan ignore lower complexity termsExamples2 n + 100 O(n)n log(n) + 10 n O(nlog(n))½ n2 + 100 n O(n2)n3 + 100 n2 O(n3)1/100 2n + 100 n4 O(2n)Complexity Examples 2n + 100 O(n)0100000200000300000400000500000600000700000800000134912026053310682118417582081611131602n nlog(n) 2 n + 100Complexity Examples ½ n log(n) + 10 n O(nlog(n))010000020000030000040000050000060000070000080000022879178373756150629755855115012256544252n nlog(n) 1/2 n log(n) + 10 nComplexity Examples ½ n2 + 100 n O(n2)010000020000030000040000050000060000070000080000022879178373756150629755855115012256544252nlog(n) n^2 1/2 n^2 + 100 nComplexity Examples 1/100 2n + 100 n4 O(2n)11E+151E+301E+451E+601E+751E+901E+1051E+1201E+1351E+1502 13 28 49 79 120 178 260 373 533 756n^2 n^4 2^n 1 / 100 2^n + 100 n^4Comparing ComplexityCompare two algorithmsf(n), g(n)Determine which increases at faster rateAs problem size n increasesCan compare ratioIf , f() is largerIf 0, g() is largerIf constant, then same complexitylim nf(n) g(n)Complexity Comparison Exampleslog(n) vs. n½1.001n vs. n1000lim nf(n) g(n)lim nlog(n) n½0lim nf(n) g(n)lim n1.001n n1000??Not clear, use L’Hopital’s RuleL’Hopital’s RuleIf ratio is indeterminate0 / 0 or / Ratio of derivatives computes same valueCan simplify ratio by repeatedly taking derivatives of numerator & denominatorlim nf(n) g(n)lim nf'(n) g'(n)=Using L’Hopital’s Rule1.001n vs. n1000lim nf(n) g(n)lim n1.001n n1000lim nn 1.001n-1 1000 n999lim nn (n-1) 1.001n-2 1000999 n998…Additional Complexity MeasuresUpper bound Big-O (…)Represents upper bound on # stepsLower bound Big-Omega (…)Represents lower bound on # stepsCombined boundBig-Theta (…)Represents combined upper/lower bound on # stepsBest possible asymptotic solution2D Matrix Multiplication ExampleProblem C = A * BLower bound(n2) Required to examine 2D matrixUpper boundsO(n3) Basic algorithmO(n2.807) Strassen’s algorithm (1969)O(n2.376) Coppersmith & Winograd (1987)Improvements still possible (open problem)Since upper & lower bounds do not match=Additional Complexity Categories Name DescriptionNP Nondeterministic polynomial time (NP)PSPACE Polynomial spaceEXPSPACE Exponential spaceDecidable Can be solved by finite algorithmUndecidable Not solvable by finite algorithmMostly of academic interest onlyQuadratic algorithms usually too slow for large dataUse fast heuristics to provide non-optimal solutionsNP Time AlgorithmPolynomial solution possibleIf make correct guesses on how to proceedRequired for many fundamental problemsBoolean satisfiability Traveling salesman problem (TLP)Bin packingKey to solving many optimization problemsMost efficient trip routesMost efficient schedule for employeesMost efficient usage of resourcesNP Time AlgorithmProperties of NPCan be solved with exponential timeNot proven to require exponential timeCurrently solve using heuristicsNP-complete problemsRepresentative of all NP problemsSolution can be used to solve any NP problemExamplesBoolean satisfiabilityTraveling salesmanP = NP?Are NP problems solvable in polynomial time?Prove P=NPShow polynomial time solution exists for any NP-complete problemProve PNPShow no polynomial-time solution possible The expected answerImportant open problem in computer science$1 million prize offered by Clay Math InstituteAlgorithmic Complexity SummaryAsymptotic
View Full Document