4 CHAPTER ONE S.1 The most straightforward reason for analyzing an algorithm is to dis- cover its characteristics in order to evaluate its suitability for various appli- cations or compare it with other algorithms for the same application.The characteristics of interest are most often the primary resources of time and space,particularly time.Put simply,we want to know how long an imple- mentation of a particular algorithm will run on a particular computer,and how much space it will require.We generally strive to keep the analysis inde- pendent of particular implementations-we concentrate instead on obtaining results for essential characteristics of the algorithm that can be used to derive precise estimates of true resource requirements on various actual machines. In practice,achieving independence between an algorithm and char- acteristics of its implementation can be difficult to arrange.The quality of the implementation and properties of compilers,machine architecture,and other major facets of the programming environment have dramatic effects on performance.We must be cognizant of such effects to be sure the results of analysis are useful.On the other hand,in some cases,analysis of an algo- rithm can help identify ways for it to take full advantage of the programming environment. Occasionally,some property other than time or space is of interest,and the focus of the analysis changes accordingly.For example,an algorithm on a mobile device might be studied to determine the effect upon battery life, or an algorithm for a numerical problem might be studied to determine how accurate an answer it can provide.Also,it is sometimes appropriate to address multiple resources in the analysis.For example,an algorithm that uses a large amount of memory may use much less time than an algorithm that gets by with very little memory.Indeed,one prime motivation for doing a careful analysis is to provide accurate information to help in making proper tradeoff decisions in such situations. The term analysis ofalgorithms has been used to describe two quite differ- ent general approaches to putting the study of the performance of computer programs on a scientific basis.We consider these two in turn. The first,popularized by Aho,Hopcroft,and Ullman [2]and Cormen, Leiserson,Rivest,and Stein [6],concentrates on determining the growth of the worst-case performance of the algorithm(an"upper bound").A prime goal in such analyses is to determine which algorithms are optimal in the sense that a matching "lower bound"can be proved on the worst-case performance of any algorithm for the same problem.We use the term theory ofalgorithms www.it-ebooks.infoț C Ŕ ō Ŝ Š ő Ş O Ś ő §Ș.Ș Ļe most straightforward reason for analyzing an algorithm is to dis￾cover its characteristics in order to evaluate its suitability for various appli￾cations or compare it with other algorithms for the same application. Ļe characteristics of interest are most often the primary resources of time and space, particularly time. Put simply, we want to know how long an imple￾mentation of a particular algorithm will run on a particular computer, and how much space it will require. We generally strive to keep the analysis inde￾pendent of particular implementations—we concentrate instead on obtaining results for essential characteristics of the algorithm that can be used to derive precise estimates of true resource requirements on various actual machines. In practice, achieving independence between an algorithm and char￾acteristics of its implementation can be difficult to arrange. Ļe quality of the implementation and properties of compilers, machine architecture, and other major facets of the programming environment have dramatic effects on performance. We must be cognizant of such effects to be sure the results of analysis are useful. On the other hand, in some cases, analysis of an algo￾rithm can help identify ways for it to take full advantage of the programming environment. Occasionally, some property other than time or space is of interest, and the focus of the analysis changes accordingly. For example, an algorithm on a mobile device might be studied to determine the effect upon battery life, or an algorithm for a numerical problem might be studied to determine how accurate an answer it can provide. Also, it is sometimes appropriate to address multiple resources in the analysis. For example, an algorithm that uses a large amount of memory may use much less time than an algorithm that gets by with very little memory. Indeed, one prime motivation for doing a careful analysis is to provide accurate information to help in making proper tradeoff decisions in such situations. Ļe term analysis of algorithms has been used to describe two quite differ￾ent general approaches to putting the study of the performance of computer programs on a scientiŀc basis. We consider these two in turn. Ļe ŀrst, popularized by Aho, Hopcroft, and Ullman [2] and Cormen, Leiserson, Rivest, and Stein [6], concentrates on determining the growth of the worst-case performance of the algorithm (an “upper bound”). A prime goal in such analyses is to determine which algorithms are optimal in the sense that a matching “lower bound” can be proved on the worst-case performance of any algorithm for the same problem. We use the term theory of algorithms www.it-ebooks.info