Chapter 9 Asymptotic Complexity Measuring the Cost of Program Execution This chapter describes a way of measuring the cost of executing a program Execution cost comes in two forms the time required for execution and the memory requirements often referred to as space The tool we develop is of limited use in predicting how much time and space will be consumed by program execution but it is very effective in comparing the costs of different programs when those differences are important Although the tool is based on a rather sophisticated mathematics it is remarkably easy to apply in the vast majority of cases of interest Execution speed and memory requirements are important attributes of a program they are the fundamental costs of program execution A program can be too slow to be useful and in any case faster is usually better When a computer magazine reports on word processing programs they compare the time required to perform operations such as formatting word search and scrolling The space required by a program is also important contemporary word processors often cannot be run on personal computers that are 10 years old because those computers don t have sufficient space to hold the part of the program that must reside in main memory Clearly execution time and memory requirements should be important considerations in program design But how does one 2001 Donald F Stanat Stephen F Weiss Chapter 9 Complexity Page 2 compare the costs of different programs without coding them and running experiments Experimental comparisons and benchmark tests of software are important and probably always will be but they are costly and answer only very specific questions their results may be valid only for users of the specific programs and hardware used in the tests In this chapter we develop some measures of the cost of program execution based on properties that can be determined simply by consideration of the algorithms used These measures are basic tools of program design As always our tools should embody suitable abstractions To make our measures widely applicable we want to ignore the details of how a program is written for example we don t want our measure to be affected by the programming language used We also want our measure to be independent of the computer on which a program is run That leads us to base our measures of cost on algorithms rather than programs Our results will not be affected by details such as the skill of the programmer and the speed of particular instructions on specific machines Experience with programs confirms our intuition that some algorithms such as binary search are inherently fast while others such as trying to find key to a secret code can take a great deal of time Further experience shows that sometimes we have a choice between algorithms that exhibit a time space trade off that is algorithms A and B perform the same task and A runs faster than B but A requires more memory than B and we are unable to devise an algorithm that has both the speed of A and the small memory requirements of B To choose between such alternatives we must somehow characterize and quantify the differences in cost In our discussion we will often follow a long standing tradition by referring to the execution cost of an algorithm as the complexity of the algorithm We will also speak of the cost or complexity of program execution when we really mean the cost or complexity of the algorithm implemented by the program The execution time of an algorithm should characterize how long resources must be available to execute any program that implements the algorithm and the space requirements of an algorithm should measure the largest amount of memory required to hold the data and intermediate results during execution But some problem instances are less costly to solve than others for example some sorting algorithms work very quickly on an array that is already sorted and much less quickly on a list of the same size that is sorted in the reverse order This leads us to explore both the worst case complexity of an algorithm and the average case complexity The mathematical tools we ll develop enable us to do more than compare algorithms They provide a way to show mathematically that some problems are inherently more difficult than others in the sense that no algorithm can solve them faster than some lower bound This in turn enables us to show that some algorithms are optimal in the sense that according to the measures we use no algorithm can do better Thus for example we can show that if searching of a sorted list is done by comparing values binary search is optimal and linear search is not The measure of program execution cost we introduce here is broadly applicable and easily applied yet remarkably useful Our treatment will emphasize the measure of execution time but the same tools apply to the space required for program execution 1 15 2019 1 15 2019 Chapter 9 Complexity Page 3 Measuring Execution Time the time complexity of an algorithm Our measure of execution cost is based on a collection of observations abstractions and simplifying assumptions We begin by noting that algorithms are used to solve problems1 of varying size and that the cost of solving a problem increases with the problem size Choosing problem size as a basic parameter for our measure of cost is a first step in abstraction Deciding what is meant by the size of a problem requires some judgment but there is usually no disagreement If an algorithm is to sort the entries of a list then the size of the problem is the size of the list If we are to find the greatest common divisor of two positive integers the largest of the two could be taken to be the size of the problem If we are to find a name in a telephone book the number of entries in the telephone book is the size of the problem Sometimes the choice is not so clear but the issue is usually easily resolved by making the simplest choice For example in multiplying square n by n matrices the size of the problem could be taken as n the dimension of the matrices or it could be taken as n2 the number of entries in each matrix Choosing the simplest of these leads to using n The next step of our abstraction is to measure execution time by counting the number of times that crucial operations are performed when an algorithm is executed An operation is crucial to an algorithm if the algorithm can not be implemented without it For example linear search and binary search both have comparison of