CHAPTER ONE ANALYSIS OF ALGORITHMS M ATHEMATICAL studies of the properties of computer algorithms have spanned a broad spectrum,from general complexity studies to specific analytic results.In this chapter,our intent is to provide perspective on various approaches to studying algorithms,to place our field of study into context among related fields and to set the stage for the rest of the book. To this end,we illustrate concepts within a fundamental and representative problem domain:the study of sorting algorithms. First,we will consider the general motivations for algorithmic analysis. Why analyze an algorithm?What are the benefits of doing so?How can we simplify the process?Next,we discuss the theory of algorithms and consider as an example mergesort,an"optimal"algorithm for sorting.Following that, we examine the major components of a full analysis for a sorting algorithm of fundamental practical importance,quicksort.This includes the study of vari- ous improvements to the basic quicksort algorithm,as well as some examples illustrating how the analysis can help one adjust parameters to improve per- formance. These examples illustrate a clear need for a background in certain areas of discrete mathematics.In Chapters 2 through 4,we introduce recurrences, generating functions,and asymptotics-basic mathematical concepts needed for the analysis of algorithms.In Chapter 5,we introduce the symbolic method, a formal treatment that ties together much of this book's content.In Chap- ters 6 through 9,we consider basic combinatorial properties of fundamental algorithms and data structures.Since there is a close relationship between fundamental methods used in computer science and classical mathematical analysis,we simultaneously consider some introductory material from both areas in this book. 1.1 Why Analyze an Algorithm?There are several answers to this basic ques- tion,depending on one's frame of reference:the intended use of the algo- rithm,the importance of the algorithm in relationship to others from both practical and theoretical standpoints,the difficulty of analysis,and the accu- racy and precision of the required answer. 3 www.it-ebooks.infoC H A P T E R O N E A N A L Y S I S O F A L G O R I T HM S MATHEMATICAL studies of the properties of computer algorithms have spanned a broad spectrum, from general complexity studies to speciŀc analytic results. In this chapter, our intent is to provide perspective on various approaches to studying algorithms, to place our ŀeld of study into context among related ŀelds and to set the stage for the rest of the book. To this end, we illustrate concepts within a fundamental and representative problem domain: the study of sorting algorithms. First, we will consider the general motivations for algorithmic analysis. Why analyze an algorithm? What are the beneŀts of doing so? How can we simplify the process? Next, we discuss the theory of algorithms and consider as an example mergesort, an “optimal” algorithm for sorting. Following that, we examine the major components of a full analysis for a sorting algorithm of fundamental practical importance, quicksort. Ļis includes the study of vari￾ous improvements to the basic quicksort algorithm, as well as some examples illustrating how the analysis can help one adjust parameters to improve per￾formance. Ļese examples illustrate a clear need for a background in certain areas of discrete mathematics. In Chapters 2 through 4, we introduce recurrences, generating functions, and asymptotics—basic mathematical concepts needed for the analysis of algorithms. In Chapter 5, we introduce the symbolic method, a formal treatment that ties together much of this book’s content. In Chap￾ters 6 through 9, we consider basic combinatorial properties of fundamental algorithms and data structures. Since there is a close relationship between fundamental methods used in computer science and classical mathematical analysis, we simultaneously consider some introductory material from both areas in this book. 1.1 Why Analyze an Algorithm? Ļere are several answers to this basic ques￾tion, depending on one’s frame of reference: the intended use of the algo￾rithm, the importance of the algorithm in relationship to others from both practical and theoretical standpoints, the difficulty of analysis, and the accu￾racy and precision of the required answer. Ț www.it-ebooks.info