Algorithmic ComplexityNelson Padua-PerezBill PughDepartment of Computer ScienceUniversity of Maryland, College ParkAlgorithm 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 AlgorithmAlgorithmGuess number = 1If incorrect, increment guess by 1Repeat 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 AlgorithmAlgorithmSet Δ to n/4Guess number = n/2If too large, guess number – ΔIf too small, guess number + ΔReduce Δ by ½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 ) = 17 stepsBinary search is much more efficient!Asymptotic ComplexityComparing two linear functions205125651210271282565156412825932644n+3n/2Running TimeSizeAsymptotic 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 functions489512438256387128336645 * log2( n ) + 3log2( n )Running TimeSizeAsymptotic ComplexityComparing two functionslog2( n ) and 5 * log2( n ) + 3 behave similarlyRun time roughly increases by constant as inputsize 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 functions520256161326484016416422 n2 + 8n2Running TimeSizeAsymptotic ComplexityComparing two functionsn2 and 2 n2 + 8 behave similarlyRun time roughly increases by 4 as input sizedoublesRun time increases quadratically with input sizeFor large values of nTime(2n) / Time(n) approaches 4Both are O( n2 ) programsBig-O NotationRepresentsUpper bound on number of steps in algorithmIntrinsic efficiency of algorithm for large inputsf(n)O(…)input size# stepsFormal Definition of Big-OFunction f(n) is Ο ( g(n) ) ifFor some positive constants M, N0M × g(n) ≥ f(n), for all n ≥ N0IntuitivelyFor some coefficient M & all data sizes ≥ N0M × g(n) is always greater than f(n)Big-O Examples5n + 1000 ⇒ O(n)Select M = 6, N0 = 1000For n ≥ 10006n ≥ 5n+1000 is always trueExample ⇒ for n = 10006000 ≥ 5000 +1000Big-O Examples2n2 + 10n + 1000 ⇒ O(n2)Select M = 4, N0 = 100For n ≥ 1004n2 ≥ 2n2 + 10n + 1000 is always trueExample ⇒ for n = 10040000 ≥ 20000 + 1000 + 1000ObservationsBig 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 measureof efficiencyComparison of ComplexityComplexity 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 Examples2n + 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 Examples1/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^4Types of Case AnalysisCan analyze different types (cases) of algorithmbehaviorTypes of analysisBest caseWorst caseAverage caseTypes of Case AnalysisBest caseSmallest number of steps requiredNot very usefulExample ⇒ Find item in first place checkedTypes of Case AnalysisWorst caseLargest number of steps requiredUseful for upper bound on worst performanceReal-time applications (e.g., multimedia)Quality of service guaranteeExample ⇒ Find item in last place checkedQuicksort ExampleQuicksortOne of the fastest comparison sortsFrequently used in practiceQuicksort algorithmPick pivot value from listPartition list into values smaller & bigger than pivotRecursively sort both
View Full Document
Unlocking...