## A.5 Logarithms Logarithms are one of the mathematical tools used most in analysis of algorithms. We briefly review their properties. ### A.5.1 Definition and Properties of Logarithms The ***common Logarithm*** of a number is the power to which 10 must be raised to produce the number. If *x* is a given number, we denote its common logarithm by log *x*. Example A.6****Some common logarithms follow: [](figu522_3.jpg) Recall that the value of any nonzero number raised to the 0th power is 1. **** In general, the logarithm of a number *x* is the power to which another number *a*, called the *base*, must be raised to produce *x*. The number *a* can be any positive number other than 1, whereas *x* must be positive. That is, there is no such thing as the logarithm of a negative number or of 0. In symbols, we write log*a**x*. Example A.7****Some examples of log*a**x* follow:  **** Notice that the last result in [Example A.7](#ap-aex10) is for a number that is not an integral power of the base. Logarithms exist for all positive numbers, not just for integral powers of the base. A discussion of the meaning of the logarithm when the number is not an integral power of the base is beyond the scope of this appendix. We note here only that the logarithm is an increasing function. That is,  Therefore,  We saw in [Example A.7](#ap-aex10) that log2 7 is about 2.807, which is between 2 and 3. Listed below are some important properties of logarithms that are useful in the analysis of algorithms. **Some Properties of Logarithms** (In all cases, *a* > 1, *b* > 1, *x* > 0, and *y* > 0):  Example A.8****Some examples of applying the previous properties follow:  **** Because many calculators have a log function (recall that log means log10), the last two results in [Example A.8](#ap-aex11) show how one can use a calculator to compute a logarithm for an arbitrary base. (This is how we computed them.) We encounter the logarithm to base 2 so often in analysis of algorithms that we give it its own simple symbol. That is, we denote log2*x* by **lg *x***. From now on, we use this notation. ### A.5.2 The Natural Logarithm You may recall the number *e*, whose value is approximately 2.718281828459. Like 蟺, the number *e* cannot be expressed exactly by any finite number of decimal digits, and indeed there is not even a repeating pattern of digits in its decimal expansion. We denote log*e**x* by **ln *x***, and we call it the ***natural logarithm*** of *x*. For example,  You may wonder where we got this answer. We simply used a calculator that has an ln function. Without studying calculus, it is not possible to understand how the natural logarithm is computed and why it is called "natural." Indeed, when we merely look at *e*, the natural logarithm appears most unnatural. Although a discussion of calculus is beyond our present scope (except for some material marked ), we do want to explore one property of the natural logarithm that is important to the analysis of algorithms. With calculus it is possible to show that ln *x* is the area under the curve 1/*x* that lies between 1 and *x*. This is illustrated in the top graph in [Figure A.3](#ap-afig03) for *x* = 5. In the bottom graph in that figure, we show how that area can be approximated by summing the areas of rectangles that are each one unit wide. The graph shows that the approximation to ln 5 is  [](figap-a-3_0.jpg) Figure A.3: The shaded area in the top graph is ln 5. The combined area of the shaded rectangles in the bottom graph is an approximation to ln 5. Notice that this area is always larger than the true area. Using a calculator,. we can determine that  The area of the rectangles is not a very good approximation to ln 5. However, by the time we get to the last rectangle (the one between the *x*-values 4 and 5), the area is not much different from the area under the curve between *x* = 4 and *x* = 5. This is not the case for the first rectangle. Each successive rectangle gives a better approximation than its predecessor. Therefore, when the number is not small, the sum of the areas of the rectangles is close to the value of the natural logarithm. The following example shows the usefulness of this result. Example A.9****Suppose we wish to compute  There is no closed-form expression for this sum. However, in accordance with the preceding discussion, if *n* is not small,  When *n* is not small, the value of 1/*n* is negligible in comparison with the sum. Therefore, we can also add that term to get the result  We will use this result in some of our analyses. In general, it is possible to show that  ****