The Running Time of Programs - Stanford University

1 CHAPTER3FF FFThe Running Timeof ProgramsIn Chapter 2, we saw two radically different algorithms for sorting: selection sortand merge sort. There are, in fact, scores of algorithms for sorting. This situationis typical: every problem that can be solved at all can be solved by more than , then, should we choose an algorithm to solve a given problem? As ageneral rule, we should always pick an algorithm that is easyto understand, im-plement, and document. When performance is important, as itoften is, we alsoneed to choose an algorithm that runs quickly and uses the available computingresources efficiently.

2 We are thus led to consider the often subtle matter of how wecan measure the Running time of a program or an algorithm, andwhat steps we cantake to make a program run What This Chapter Is AboutIn this chapter we shall cover the following topics:FThe important performance measures for programsFMethods for evaluating program performanceF Big-oh notationFEstimating the Running time of Programs using the big-oh notationFUsing recurrence relations to evaluate the Running time of recursive programsThe big-oh notation introduced in Sections and simplifies the process of esti-mating the Running time of Programs by allowing us to avoid dealing with constantsthat are almost impossible to determine.

3 Such as the number of machine instructionsthat will be generated by a typical C compiler for a given source introduce the techniques needed to estimate the Running time of programsin stages. In Sections and we present the methods usedto analyze programs8990 THE Running time OF Programs with no function calls. Section extends our capability to Programs with calls tononrecursive functions. Then in Sections and we show how to deal withrecursive functions. Finally, Section discusses solutions to recurrence relations,which are inductive definitions of functions that arise whenwe analyze the runningtime of recursive Choosing an AlgorithmIf you need to write a program that will be used once on small amounts of dataand then discarded, then you should select the easiest-to-implement algorithm youknow, get the program written and debugged, and move on to something else.

4 How-ever, when you need to write a program that is to be used and maintained by manypeople over a long period of time , other issues arise. One is the understandability, orsimplicity, of the underlying algorithm. Simple algorithms are desirable for severalSimplicityreasons. Perhaps most important, a simple algorithm is easier to implement cor-rectly than a complex one. The resulting program is also lesslikely to have subtlebugs that get exposed when the program encounters an unexpected input after ithas been in use for a substantial period of should be written clearly and documented carefully so that they canClaritybe maintained by others.

5 If an algorithm is simple and understandable, it is easierto describe. With good documentation, modifications to the original program canreadily be done by someone other than the original writer (who frequently will notbe available to do them), or even by the original writer if theprogram was done sometime earlier. There are numerous stories of programmers whowrote efficient andclever algorithms, then left the company, only to have theiralgorithms ripped outand replaced by something slower but more understandable bysubsequent main-tainers of the a program is to be run repeatedly, its efficiency and that of its underlyingEfficiencyalgorithm become important.

6 Generally, we associate efficiency with the time ittakes a program to run, although there are other resources that a program sometimesmust conserve, such as1. The amount of storage space taken by its The amount of traffic it generates on a network of The amount of data that must be moved to and from large problems, however, it is the Running time that determines whether a givenprogram can be used, and Running time is the main topic of thischapter. Weshall, in fact, take the efficiency of a program to mean the amount of time it takes,measured as a function of the size of its , understandability and efficiency are conflicting aims.

7 For example, thereader who compares the selection sort program of Fig. with the merge sortprogram of Fig. will surely agree that the latter is not only longer, but quitea bit harder to understand. That would still be true even if wesummarized theexplanation given in Sections and by placing well-thought-out comments inthe Programs . As we shall learn, however, merge sort is much more efficient thanselection sort, as long as the number of elements to be sortedis a hundred or , this situation is quite typical: algorithms that are efficient for Running TIME91amounts of data tend to be more complex to write and understand than are therelatively inefficient understandability, or simplicity, of an algorithm is somewhat can overcome lack of simplicity in an algorithm, to a certain extent, by explain-ing the algorithm well in comments and program documentation.

8 The documentorshould always consider the person who reads the code and its comments: Is a rea-sonably intelligent person likely to understand what is being said, or are furtherexplanation, details, definitions, and examples needed?On the other hand, program efficiency is an objective matter: aprogram takeswhat time it takes, and there is no room for dispute. Unfortunately, we cannot runthe program on all possible inputs which are typically infinite in number. Thus,we are forced to make measures of the Running time of a programthat summarizethe program s performance on all inputs, usually as a singleexpression such as n2.

9 How we can do so is the subject matter of the balance of this Measuring Running TimeOnce we have agreed that we can evaluate a program by measuring its runningtime, we face the problem of determining what the Running time actually is. Thetwo principal approaches to summarizing the Running time are1. Benchmarking2. AnalysisWe shall consider each in turn, but the primary emphasis of this chapter is on thetechniques for analyzing a program or an comparing two or more Programs designed to do the same set of tasks, it iscustomary to develop a small collection of typical inputs that can serve is, we agree to accept the benchmark inputs as representative of thejob mix; a program that performs well on the benchmark inputsis assumed toperform well on all example, a benchmark to evaluate sorting Programs mightcontain onesmall set of numbers, such as the first 20 digits of.

10 One medium set, such as theset of zip codes in Texas; and one large set, such as the set of phone numbers in theBrooklyn telephone directory. We might also want to check that a program worksefficiently (and correctly) when given an empty set of elements to sort, a singletonset, and a list that is already in sorted order. Interestingly, some sorting algorithmsperform poorly when given a list of elements that is already selection sort nor merge sort is among these; they take approximately the same timeon a sorted list as they would on any other list of the same Running time OF PROGRAMSThe 90-10 RuleIn conjunction with benchmarking, it is often useful to determine where the programunder consideration is spending its time .