Algorithmic ComplexityWhere We AreAlgorithm EfficiencyBenchmarkingSlide 5Asymptotic AnalysisSearch ExampleLinear Search AlgorithmSlide 9Binary Search AlgorithmSlide 11Slide 12Search ComparisonAsymptotic ComplexitySlide 15Slide 16Slide 17Slide 18Slide 19ObservationsComparison of ComplexityAlgorithmic Complexity Fawzi EmadChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkWhere We AreOO software developmentAlgorithms & data structuresAsymptotic analysisData structuresLinearHierarchicalUnstructuredAdvanced Java CollectionsThreadsSo farComing upAlgorithm EfficiencyEfficiencyAmount of resources used by algorithmTime, spaceMeasuring efficiencyBenchmarkingAsymptotic analysisBenchmarkingApproachPick some desired inputsActually run implementation of algorithmMeasure time & space neededIndustry benchmarksSPEC – CPU performanceMySQL – Database applicationsWinStone – Windows PC applicationsMediaBench – Multimedia applicationsLinpack – Numerical scientific applicationsBenchmarkingAdvantagesPrecise information for given configurationImplementation, hardware, inputsDisadvantagesAffected by configurationData sets (usually too small)HardwareSoftwareAffected by special cases (biased inputs)Does not measure intrinsic efficiencyAsymptotic AnalysisApproachMathematically analyze efficiencyCalculate time as function of input size nT O[ f(n) ]T is on the order of f(n)“Big O” notationAdvantagesMeasures intrinsic efficiencyDominates efficiency for large input sizesSearch ExampleNumber guessing gamePick a number between 1…nGuess a numberAnswer “correct”, “too high”, “too low”Repeat guesses until correct number guessedLinear Search AlgorithmAlgorithm1. Guess number = 12. If incorrect, increment guess by 13. Repeat until correctExampleGiven number between 1…100Pick 20Guess sequence = 1, 2, 3, 4 … 20Required 20 guessesLinear Search AlgorithmAnalysis of # of guesses needed for 1…nIf number = 1, requires 1 guessIf number = n, requires n guessesOn average, needs n/2 guessesTime = O( n ) = Linear timeBinary Search AlgorithmAlgorithm1. Set to n/42. Guess number = n/23. If too large, guess number – 4. If too small, guess number + 5. Reduce by ½6. Repeat until correctBinary Search AlgorithmExampleGiven number between 1…100Pick 20Guesses = 50, = 25, Answer = too large, subtract 25, = 12 , Answer = too large, subtract 13, = 6, Answer = too small, add 19, = 3, Answer = too small, add 22, = 1, Answer = too large, subtract 21, = 1, Answer = too large, subtract 20Required 7 guessesBinary Search AlgorithmAnalysis of # of guesses needed for 1…nIf number = n/2, requires 1 guessIf number = 1, requires log2( n ) guessesIf number = n, requires log2( n ) guessesOn average, needs log2( n ) guessesTime = O( log2( n ) ) = Log timeSearch ComparisonFor number between 1…100Simple algorithm = 50 stepsBinary search algorithm = log2( n ) = 7 stepsFor number between 1…100,000Simple algorithm = 50,000 stepsBinary search algorithm = log2( n ) = 77 stepsBinary search is much more efficient!Asymptotic ComplexityComparing two linear functionsSize Running Timen/2 4n+364 32 259128 64 515256 128 1027512 256 2051Asymptotic ComplexityComparing two functionsn/2 and 4n+3 behave similarlyRun time roughly doubles as input size doublesRun time increases linearly with input sizeFor large values of nTime(2n) / Time(n) approaches exactly 2Both are O(n) programsAsymptotic ComplexityComparing two log functionsSize Running Timelog2( n ) 5 * log2( n ) + 364 6 33128 7 38256 8 43512 9 48Asymptotic ComplexityComparing two functionslog2( n ) and 5 * log2( n ) + 3 behave similarlyRun time roughly increases by constant as input size doublesRun time increases logarithmically with input sizeFor large values of nTime(2n) – Time(n) approaches constantBase of logarithm does not matterSimply a multiplicative factorlogaN = (logbN) / (logba) Both are O( log(n) ) programsAsymptotic ComplexityComparing two quadratic functionsSize Running Timen22 n2 + 82 4 164 16 408 64 13216 256 520Asymptotic ComplexityComparing two functionsn2 and 2 n2 + 8 behave similarlyRun time roughly increases by 4 as input size doublesRun time increases quadratically with input sizeFor large values of nTime(2n) / Time(n) approaches 4Both are O( n2 ) programsObservationsBig O categoriesO(log(n))O(n)O(n2)For large values of nAny O(log(n)) algorithm is faster than O(n)Any O(n) algorithm is faster than O(n2)Asymptotic complexity is fundamental measure of efficiencyComparison of
View Full Document