AnalysisofAlgorithms/Slide6Worst- / average- / best-caseWorst-case runningtimeof an algorithmMThe longest running time forany input of size nAnupperbound ontherunning timefor anyinput=guarantee that the algorithm will never take longerExample:Sort a set of numbers inincreasingorder,and thedataisindecreasing orderTheworstcasecanoccurfairlyoftenE.g.in searchinga databaseforaparticularpieceof informationBest-case running timesorta set of numbers in increasing order,and the data isalreadyin increasing orderAverage-caserunningtimeMay be difficultto define what"average"means
Analysis of Algorithms / Slide 6 Worst- / average- / best-case * Worst-case running time of an algorithm n The longest running time for any input of size n n An upper bound on the running time for any input guarantee that the algorithm will never take longer n Example: Sort a set of numbers in increasing order; and the data is in decreasing order n The worst case can occur fairly often 1E.g. in searching a database for a particular piece of information * Best-case running time n sort a set of numbers in increasing order; and the data is already in increasing order * Average-case running time n May be difficult to define what “average” means
AnalysisofAlgorithms/Slide7Running-time of algorithmsBoundsareforthealgorithms,NOTfor programsprograms are just implementations of an algorithm,and theimplementationdetails ofthe program donot affect theboundsBoundsareforalgorithms,NOTfor problemsMIAproblemcanbesolvedbyseveral differentalgorithmssome aremore efficient than othersAlgorithms areoftenwritteninpseudo-codesWeuse‘almost'somethinglikeC++
Analysis of Algorithms / Slide 7 Running-time of algorithms * Bounds are for the algorithms, NOT for programs n programs are just implementations of an algorithm, and the implementation details of the program do not affect the bounds * Bounds are for algorithms, NOT for problems n A problem can be solved by several different algorithms, some are more efficient than others * Algorithms are often written in pseudo-codes n We use ‘almost’ something like C++
AnalysisofAlgorithms/Slide8Algorithm AnalysisWeonly analyze correctalgorithmsAnalgorithmis correct If,foreveryinputinstance,ithaltswiththecorrectoutputIncorrectalgorithmsMightnothalt atall onsomeinput instancesMighthaltwithotherthanthedesiredanswerAnalyzinganalgorithmPredicting the resources that the algorithm requiresResourcesincludeMemoryComputationaltime (usuallymost important)Nototherssuchas communicationbandwidth
Analysis of Algorithms / Slide 8 Algorithm Analysis * We only analyze correct algorithms * An algorithm is correct n If, for every input instance, it halts with the correct output * Incorrect algorithms n Might not halt at all on some input instances n Might halt with other than the desired answer * Analyzing an algorithm n Predicting the resources that the algorithm requires n Resources include 1Memory 1Computational time (usually most important) 1Not others such as communication bandwidth
AnalysisofAlgorithms/Slide9Machine model and input sizeMachinemodelassumedBasicinstructionsInstructionsareexecutedoneafteranother,withnoconcurrentoperations=NotparallelcomputersFactors affecting therunningtimecomputercompileralgorithmusedinput to the algorithmThe content of the input affects the runningtimetypically,theinputsize(numberofitemsintheinput)isthemainconsiderationE.g.sortingproblem=thenumberof itemstobesortedE.g.multiplytwo matricestogether=thetotal numberofelementsinthetwomatrices
Analysis of Algorithms / Slide 9 * Machine model assumed n Basic instructions n Instructions are executed one after another, with no concurrent operations Not parallel computers * Factors affecting the running time n computer n compiler n algorithm used n input to the algorithm 1The content of the input affects the running time 1typically, the input size (number of items in the input) is the main consideration l E.g. sorting problem the number of items to be sorted l E.g. multiply two matrices together the total number of elements in the two matrices Machine model and input size
AnalysisofAlgorithms/Slide10Growth Ratecg(n)f(n)nnof(n)=O(g(n)The idea is to establish a relative order among functions for largeMn3c,n>Osuchthatf(N)≤cg(N)whenN≥no f(N)growsnofasterthang(N)for“largeN
Analysis of Algorithms / Slide 10 Growth Rate * The idea is to establish a relative order among functions for large n * c , n0 > 0 such that f(N) c g(N) when N n0 * f(N) grows no faster than g(N) for “large” N