Measuring Execution Time: the time complexity of an algorithmComparing Complexity FunctionsHow Do We Use It?The Principal Complexity Classes(1) functions. (Constant complexity)(log n) functions. (Logarithmic complexity)(n) functions. (Linear complexity)(n log n) functions. (n log n complexity)(n2) functions. (Quadratic complexity)(n3) functions. (Cubic complexity)(2n) functions. (Exponential complexity)(n!) functions. (Factorial complexity)Finding complexity of non-recursive code:Finding the Complexity of Recursive SubroutinesSolutions to recurrence equationsAverage Case ComplexitySpace complexityUsing complexity resultsSidebar on LogarithmsExercises:Chapter 9: Asymptotic Complexity: Measuring the Cost of Program Execution.Chapter 9Asymptotic Complexity: Measuring the Cost of Program Execution.This chapter describes a way of measuring the cost of executing aprogram. Execution cost comes in two forms: the time required forexecution, and the memory requirements, often referred to as ‘space’. Thetool we develop is of limited use in predicting how much time and spacewill be consumed by program execution, but it is very effective incomparing the costs of different programs when those differences areimportant. Although the tool is based on a rather sophisticatedmathematics, it is remarkably easy to apply in the vast majority of cases ofinterest.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. WeissChapter 9 Complexity Page 2compare the costs of different programs without coding them and running experiments? Experimental comparisons and ‘benchmark tests’ of software are important (and probablyalways 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, andwe 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 canshow 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/2019Chapter 9 Complexity Page 3Measuring Execution Time: the time complexity of an algorithmOur 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