SI.I ANALY SIS OF ALGORITHMS 5 to refer to this type of analysis.It is a special case of computational complexity, the general study of relationships between problems,algorithms,languages, and machines.The emergence of the theory of algorithms unleashed an Age of Design where multitudes of new algorithms with ever-improving worst- case performance bounds have been developed for multitudes of important problems.To establish the practical utility of such algorithms,however,more detailed analysis is needed,perhaps using the tools described in this book. The second approach to the analysis ofalgorithms,popularized by Knuth [17][18][19][20][22],concentrates on precise characterizations of the best- case,worst-case,and average-case performance ofalgorithms,using a method- ology that can be refined to produce increasingly precise answers when de- sired.A prime goal in such analyses is to be able to accurately predict the performance characteristics of particular algorithms when run on particular computers,in order to be able to predict resource usage,set parameters,and compare algorithms.This approach is scientific:we build mathematical mod- els to describe the performance of real-world algorithm implementations, then use these models to develop hypotheses that we validate through ex- perimentation. We may view both these approaches as necessary stages in the design and analysis of efficient algorithms.When faced with a new algorithm to solve a new problem,we are interested in developing a rough idea of how well it might be expected to perform and how it might compare to other algorithms for the same problem,even the best possible.The theory of algo- rithms can provide this.However,so much precision is typically sacrificed in such an analysis that it provides little specific information that would al- low us to predict performance for an actual implementation or to properly compare one algorithm to another.To be able to do so,we need details on the implementation,the computer to be used,and,as we see in this book, mathematical properties of the structures manipulated by the algorithm.The theory of algorithms may be viewed as the first step in an ongoing process of developing a more refined,more accurate analysis;we prefer to use the term analysis ofalgorithms to refer to the whole process,with the goal of providing answers with as much accuracy as necessary. The analysis of an algorithm can help us understand it better,and can suggest informed improvements.The more complicated the algorithm,the more difficult the analysis.But it is not unusual for an algorithm to become simpler and more elegant during the analysis process.More important,the www.it-ebooks.info§Ș.Ș A Ś ō Ř ť ş ŕ ş ś Œ A Ř œ ś Ş ŕ Š Ŕ ř ş Ȝ to refer to this type of analysis. It is a special case of computational complexity, the general study of relationships between problems, algorithms, languages, and machines. Ļe emergence of the theory of algorithms unleashed an Age of Design where multitudes of new algorithms with ever-improving worst￾case performance bounds have been developed for multitudes of important problems. To establish the practical utility of such algorithms, however, more detailed analysis is needed, perhaps using the tools described in this book. Ļe second approach to the analysis of algorithms, popularized by Knuth [17][18][19][20][22], concentrates on precise characterizations of the best￾case, worst-case, and average-case performance of algorithms, using a method￾ology that can be reŀned to produce increasingly precise answers when de￾sired. A prime goal in such analyses is to be able to accurately predict the performance characteristics of particular algorithms when run on particular computers, in order to be able to predict resource usage, set parameters, and compare algorithms. Ļis approach is scientiŀc: we build mathematical mod￾els to describe the performance of real-world algorithm implementations, then use these models to develop hypotheses that we validate through ex￾perimentation. We may view both these approaches as necessary stages in the design and analysis of efficient algorithms. When faced with a new algorithm to solve a new problem, we are interested in developing a rough idea of how well it might be expected to perform and how it might compare to other algorithms for the same problem, even the best possible. Ļe theory of algo￾rithms can provide this. However, so much precision is typically sacriŀced in such an analysis that it provides little speciŀc information that would al￾low us to predict performance for an actual implementation or to properly compare one algorithm to another. To be able to do so, we need details on the implementation, the computer to be used, and, as we see in this book, mathematical properties of the structures manipulated by the algorithm. Ļe theory of algorithms may be viewed as the ŀrst step in an ongoing process of developing a more reŀned, more accurate analysis; we prefer to use the term analysis of algorithms to refer to the whole process, with the goal of providing answers with as much accuracy as necessary. Ļe analysis of an algorithm can help us understand it better, and can suggest informed improvements. Ļe more complicated the algorithm, the more difficult the analysis. But it is not unusual for an algorithm to become simpler and more elegant during the analysis process. More important, the www.it-ebooks.info