Analysis is the key to being able to understand algorithms sufficiently well that we can apply them effectively to practical problems. Although we cannot do extensive experimentation and deep mathematical analysis on each and every program that we run, we can work within a basic framework involving both empirical testing and approximate analysis that can help us to know the important facts about the performance characteristics of our algorithms so that we may compare those algorithms and can apply them to practical problems.
The very idea of describing the performance of a complex algorithm accurately with a mathematical analysis seems a daunting prospect at first, and we do often call on the research literature for results based on detailed mathematical study. Although it is not our purpose in this tutorial to cover methods of analysis or even to summarize these results, it is important for us to be aware at the outset that we are on firm scientific ground when we want to compare different methods. Moreover, a great deal of detailed information is available about many of our most important algorithms through careful app of relatively few elementary techniques. We do highlight basic analytic results and methods of analysis throughout the tutorial, particularly when such activities help us to understand the inner workings of fundamental algorithms. Our primary goal in this chapter is to provide the context and the tools that we need to work intelligently with the algorithms themselves.
The example in provides a context that illustrates many of the basic concepts of algorithm analysis, so we frequently refer back to the performance of union–find algorithms to make particular points concrete. We also consider a detailed pair of new examples in .
Analysis plays a role at every point in the process of designing and implementing algorithms. At first, as we saw, we can save factors of thousands or millions in the running time with appropriate algorithm design choices. As we consider more efficient algorithms, we find it more of a challenge to choose among them, so we need to study their properties in more detail. In pursuit of the best (in some precise technical sense) algorithm, we find both algorithms that are useful in practice and theoretical questions that are challenging to resolve.
Complete coverage of methods for the analysis of algorithms is the subject of a tutorial in itself (see reference section), but it is worthwhile for us to consider the basics here so that we can
Most important, algorithms and their analyses are often intertwined. In this tutorial, we do not delve into deep and difficult mathematical derivations, but we do use sufficient mathematics to be able to understand what our algorithms are and how we can use them effectively.