AnalysisofAlgorithms/Slide1IntroductionWhyneed algorithm analysis?writingaworkingprogramisnotgoodenoughWhichprogram/algorithmisbetter?The program may be inefficient (in terms of runningtime) !lftheprogramisrunonalargedataset,thentherunning timebecomes an issueWhatisanalysis?Aroughcounting'of thenumber of operations
Analysis of Algorithms / Slide 1 Introduction *Why need algorithm analysis ? nwriting a working program is not good enough nWhich program/algorithm is better? nThe program may be inefficient (in terms of running time) ! nIf the program is run on a large data set, then the running time becomes an issue *What is analysis? nA rough ‘counting’ of the number of operations
AnalysisofAlgorithms/Slide2Example: Selection ProblemGivena listof Nnumbers,determinethekthlargest,wherek≤NAlgorithm 1:(1)ReadNnumbers intoanarray(2)Sort thearray indecreasing order by somesimplealgorithm(3) Return the element in position k
Analysis of Algorithms / Slide 2 Example: Selection Problem *Given a list of N numbers, determine the kth largest, where k N. *Algorithm 1: (1) Read N numbers into an array (2) Sort the array in decreasing order by some simple algorithm (3) Return the element in position k
AnalysisofAlgorithms/Slide3Algorithm2:(1)Readthefirstkelementsintoanarrayandsortthemindecreasingorder(2) Each remaining element is read one by onelf smallerthanthek-thelement,thenitisignoredOtherwise,it isplaced initscorrectspot inthe arraybumping one element out of the array(3)Theelement inthekthpositionisreturned astheanswer
Analysis of Algorithms / Slide 3 *Algorithm 2: (1) Read the first k elements into an array and sort them in decreasing order (2) Each remaining element is read one by one 1If smaller than the k-th element, then it is ignored 1Otherwise, it is placed in its correct spot in the array, bumping one element out of the array. (3) The element in the kth position is returned as the answer
AnalysisofAlgorithms/Slide4Which algorithmisbetterwhenIN=100andk=100?■N=100andk=1?Whathappenswhen■N=1,000.000andk=500000?Wecomebackaftersortinganalysis,andthereexistbetteralgorithms
Analysis of Algorithms / Slide 4 * Which algorithm is better when n N =100 and k = 100? n N =100 and k = 1? * What happens when n N = 1,000,000 and k = 500,000? * We come back after sorting analysis, and there exist better algorithms
AnalysisofAlgorithms/Slide5Different approachesEmpirical:runanimplementedsystemonreal-world data.Notion ofbenchmarksSimulational:run animplemented system onsimulateddata.Analytical:usetheoretic-model data with atheoretical model system.We do this here!
Analysis of Algorithms / Slide 5 Different approaches *Empirical: run an implemented system on real-world data. Notion of benchmarks. *Simulational: run an implemented system on simulated data. *Analytical: use theoretic-model data with a theoretical model system. We do this here!