COMP 2210 Course Notes:Algorithm AnalysisDr. HendrixComputer Science and Software EngineeringAuburn UniversityAcknowledgementsPortions of these notes were adapted from resourcesdeveloped by Sahni (Data Structures, Algorithms, and Applications), Carrano and Savitch (Data Structures and Abstractions with Java), and Lewis and Chase (Java Software Structures).Evaluating AlgorithmsAlgorithms and programs can be evaluated along many lines including:SimplicityClarityScalabilityRobustnessReusabilityMany of these criteria are subjective. An objective criterion that is of great importance is efficiency:Amount of time required to runAmount of memory consumedAmount of network bandwidth consumedAmount of external storage I/OCalculating Running TimeExperimentationAn empirical(kinh nghiem) approachAssemble collections of appropriate inputs and empirically study its performance. Then make projections based on this data.Not always straightforward (de lam)AnalysisA theoretical approachExpress the running time of an algorithm as a function of some instance characteristic, normally “problem size”Worst case, average case, best caseMajor, important units of work performed in the algorithm are normally used as surrogates(dai dien) for units of time.Measuring Algorithm EfficiencyThree algorithms for computing 1 + 2 + … n for...