DOC PREVIEW
UMD CMSC 132 - Algorithmic Complexity

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

UMD CMSC 132 - Algorithmic Complexity

Documents in this Course
Notes

Notes

8 pages

Recursion

Recursion

12 pages

Sorting

Sorting

31 pages

HTML

HTML

7 pages

Trees

Trees

19 pages

HTML

HTML

18 pages

Trees

Trees

19 pages

Honors

Honors

19 pages

Lecture 1

Lecture 1

11 pages

Quiz #3

Quiz #3

2 pages

Hashing

Hashing

21 pages

Load more
Download Algorithmic Complexity
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Algorithmic Complexity and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Algorithmic Complexity 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?