SummaryofAlgoAnalysis/SlideAlgorithm complexityProblems→algorithms→programsBoundsareforthealgorithms,ratherthanprogramsprograms are just implementations of an algorithm,andalmostalwaysthedetails of theprogramdonotaffecttheboundsAlgorithmsareoftenwritteninpseudo-codesWeusealmost'something likeC++Boundsareforalgorithms,ratherthanproblemsAproblemcanbesolvedwithseveralalgorithms,somearemoreefficientthanothers
Summary of Algo Analysis / Slide 1 Algorithm complexity Bounds are for the algorithms, rather than programs programs are just implementations of an algorithm, and almost always the details of the program do not affect the bounds Algorithms are often written in pseudo-codes We use ‘almost’ something like C++. Bounds are for algorithms, rather than problems A problem can be solved with several algorithms, some are more efficient than others Problems → algorithms → programs
SummaryofAlgoAnalysis/Slide2Worst- / average- / best-caseWorst-caserunningtimeof analgorithmThe longestrunning time forany input of size nAn upper bound on the running time for any inputguarantee that the algorithm will never take longerExample:Sort a set of numbers in increasing order;and the data isindecreasingorderTheworst case can occurfairlyoftenE.g.insearching a database fora particular piece ofinformationBest-caserunningtimesurta set of rumbers in increasing order, and the data is already inincreasrgorderAverage-case running timeMaybe difficultto detinewhat"average"means
Summary of Algo Analysis / Slide 2 Worst- / average- / best-case Worst-case running time of an algorithm The longest running time for any input of size n An upper bound on the running time for any input guarantee that the algorithm will never take longer Example: Sort a set of numbers in increasing order; and the data is in decreasing order The worst case can occur fairly often E.g. in searching a database for a particular piece of information Best-case running time sort a set of numbers in increasing order; and the data is already in increasing order Average-case running time May be difficult to define what “average” means
SummaryofAlgoAnalysis/Slide3Asymptotic notationsUpper bound O(g(N)LowerboundQ(g(N)Tight bound @(g(N))
Summary of Algo Analysis / Slide 3 Asymptotic notations Upper bound O(g(N) Lower bound (g(N)) Tight bound (g(N))
SummaryofAlgoAnalysis/Slide4Upper bound O(g(N) can be arbitrarily high .Lower bound Q(g(N)) can be arbitrarily lowMost ofestimations,often written as O(*),are tightbound o(*)Wedon'twriteo(*)becausefor many algorithms,wedon't knowthelowerbound,sotheoretically it's notyetthe tight bound O(*),butthe best or the‘lowestupperboundO(*)sofar.To getthetightbound,weneed to estimate the lowerbound
Summary of Algo Analysis / Slide 4 Upper bound O(g(N) can be arbitrarily high . Lower bound (g(N)) can be arbitrarily low . Most of estimations, often written as O(*), are tight bound (*) We don’t write (*) because for many algorithms, we don’t know the lower bound, so theoretically it’s not yet the tight bound (*), but the best or the ‘lowest’ upper bound O(*) so far . To get the tight bound, we need to estimate the lower bound
SummaryofAlgoAnalysis/Slide5Lowerbound,usuallyharderthanupperboundtoprove,informallyfindoneinputexample (ofcourse,wemayfind aneasierone,butweneedtocomeupwithasufficientlydifficultonetoaccommodateourestimator),thatinputhas to do‘atleastan amountofworkthat amount is a lower boundConsiderasequenceofo,1,2,...,N-1,andsearchfor0Atleast logN steps ifN=2kAn input of size n must takeat least log N stepsSo the lowerbound is Omega(log N)So the bound is tight,Theta(log N)
Summary of Algo Analysis / Slide 5 Consider a sequence of 0, 1, 2, ., N-1, and search for 0 At least log N steps if N = 2^k An input of size n must take at least log N steps So the lower bound is Omega(log N) So the bound is tight, Theta(log N) Lower bound, usually harder than upper bound to prove, informally, find one input example (of course, we may find an easier one, but we need to come up with a sufficiently difficult one to accommodate our estimator), that input has to do ‘at least’ an amount of work that amount is a lower bound