## B.4 Extending Results for *n*, a Power of a Positive Constant *b*, to *n* in General It is assumed in the material that follows that you are familiar with the material in [Chapter 1](LiB0008.html#16). In the case of some recursive algorithms, we can readily determine the exact time complexity only when *n* is a power of some base *b*, where *b* is a positive constant. Often the base *b* is 2. This is true in particular for many divide-and-conquer algorithms (see [Chapter 2](LiB0014.html#141)). Intuitively, it seems that a result that holds for *n* a power of *b* should approximately hold for *n* in general. For example, if for some algorithm we establish that  for *n* a power of 2, it seems that for *n* in general we should be able to conclude that  It turns out that usually we can draw such a conclusion. Next we discuss situations in which this is the case. First we need some definitions. These definitions apply to arbitrary functions whose domains and ranges are any subsets of the real numbers, but we state them for complexity functions (that is, functions that map the positive integers to the positive reals) because these are the functions that interest us here. Definition A complexity function *f* (*n*) is called ***strictly increasing*** if *f* (*n*) always gets larger as *n* gets larger. That is, if *n*1 > *n*2, then  The function shown in [Figure B.1(a)](#ap-bfig01) is strictly increasing. (For clarity, the domains of the functions in [Figure B.1](#ap-bfig01) are all the nonnegative reals.) Many of the functions we encounter in algorithm analysis are strictly increasing for nonnegative values of *n*. For example, lg *n, n, n*, lg *n, n*2 and 2*n* are all strictly increasing as long as *n* is nonnegative. [](figap-b-1_0.jpg) Figure B.1: Four functions. Definition A complexity function *f* (*n*) is called ***nondecreasing*** if *f* (*n*) never gets smaller as *n* gets larger. That is, if *n*1 > *n*2, then  Any strictly increasing function is nondecreasing, but a function that can level out is nondereasing without being strictly increasing. The function shown in [Figure B.1(b)](#ap-bfig01) is an example of such a function. The function in [Figure B.1 (c)](#ap-bfig01) is not nondecreasing. The time (or memory) complexities of most algorithms are ordinarily nondecreasing because the time it takes to process an input usually does not decrease as the input size becomes larger. Looking at [Figure B.1](#ap-bfig01), it seems that we should be able to extend an analysis for *n* a power of *b* to *n* in general as long as the function is nondecreasing. For example, suppose we have determined the values of *f*(*n*) for *n* a power of 2. In case of the function in Figure B.1(c), anything can happen between, say, 23 = 8 and 24 = 16. Therefore, nothing can be concluded about the behavior of the function between 8 and 16 from the values at 8 and 16. However, in the case of a nondecreasing function *f* (*n*), if 8 ≤ *n* ≤ 16 then  So it seems that we should be able to determine the order of *f* (*n* from the values of *f* (*n*) for *n* a power of 2. What seems to be true intuitively can indeed be proven for a large class of functions. Before giving a theorem stating this, we recall that order has to do only with long-range behavior. Because initial values of a function are unimportant, the theorem requires only that the function be eventually nondecreasing. We have the following difinition: Definition A complexity function *f* (*n*) is called ***eventually nondecreasing*** if for all *n* past some point the function never gets smaller as *n* gets larger. That is, there exists an *N* such that if *n*1 > *n*2*N*, then  Any nondecreasing function is eventually nondecreasing. The function shown in [Figure 3.1(d)](LiB0025.html#260) is an example of an eventually nondecreasing function that is not nondecreasing. We need the following definition before we give the theorem for extending the results for *n* a power of *b*: Definition A complexity function *f* (*n*) is called ***smooth*** if *f* (*n*) is eventually nondecreasing and if  Example B.23****The functions lg *n*, *n* lg *n*, and *nk*, where *k* ≥ 0, are all smooth. We show this for lg *n*. In the exercises you are asked to show it for the other functions. We have already noted that lg *n* is eventually nondecreasing. As to the second condition, we have  **** Example B.24****The function 2*n* is not smooth, because the Properties of Order in [Section 1.4.2](LiB0011.html#85) in [Chapter 1](LiB0008.html#16) imply that  Therefore,  **** We now state the theorem that enables us to generalize results obtained for *n* a power of *b*. The proof appears near the end of this appendix. Theorem B.4**** Let *b* ≥ 2 be an integer, let *f* (*n*) be a smooth complexity function, and let *T* (*n*) be an eventually nondecreasing complexity function. If  then  Furthermore, the same implication holds if Θ is replaced by "big *O*," Ω, or "small *o*." **** By "*T* (*n*) ∊ Θ (*f* (*n*)) for *n* a power of *b*," we mean that the usual conditins for Θ are known to hold when *n* is restricted to being a power of *b*. Notice in [Theorem B.4](#ap-bex29) the additional requirement that *f* (*n*) be smooth. Next we apply [Theorem B.4](#ap-bex29) Example B.25**** Suppose for some comlexity function we establish that  When *n* is a power of 2, we have the recurrence in [Example B.18](LiB0103.html#1417). Therefore, by that example,  Because lg *n* is smooth, we need only show that *T* (*n*) is eventually nondecreasing in order to apply [Theorem B.4](#ap-bex29) to conclude that  One might be tempted to conclude that *T* (*n*) is eventually nondecreasing from the fact that lg *n* + 1 is eventually nondecreasing. However, we cannot do this because we know only that *T* (*n*) = lg *n* + 1 when *n* is a power of 2. Given only this fact, *T* (*n*) could exhibit any possible behavior in between powers of 2. We show that *T* (*n*) is eventually nondecreasing by using induction to establish for *n* ≥ 2 that if 1 ≤ *k* < *n*, then  Induction base: For *n* = 2,  Therefore,  Induction hypothesis: One way to make the induction hypothesis is to assume that the statement is true for all *m* ≤ *n*. Then, as usual, we show that it is true for *n* + 1. This is the way we need it to be stated here. Let *n* be an arbitrary integer greater than or equal to 2. Assume for all *m* ≤ *n* that if *k* < *m*, than  Induction step: Because in the induction hypothesis we assumed for *k < n* that  we need only show that  To that end, it is not hard to see that if *n* ≥ 1, then  Therefore, by the induction hypothesis,  Using the recurrence, we have  and we are done. **** Finally, we develop a general method for determining the order of some common recurrences. Theorem B.5****Suppose a complexity function *T* (*n*) is eventually nondecreasing and satisfies  where *b* ≥ 2 and *k* ≥ 0 are constant integers, and *a*, *c*, and *d* are constants such that *a* > 0, *c* > 0, and *d* ≥ 0. Then  Furthermore, if, in the statement of the recurrence,  is replaced by  then Result B.5 holds with "big *O*" or Ω, respectively, replacing Θ. **** We can prove this theorem by solving the general recurrence using the characteristic equation and then applying [Theorem B.4](#ap-bex29). Example applications of [Theorem B.5](#ap-bex31) follow. Example B.26****Suppose that *T* (*n*) is eventually nondecreasing and satisfies  By [Theorem B.5](#ap-bex31), because 8 42,  **** Example B.27****Suppose that *T* (*n*) is eventually nondecreasing and satisfies  By [Theorem B.5](#ap-bex31), because 9 > 31,  **** [Theorem B.5](#ap-bex31) was stated in order to introduce an important theorem as simply as possible. It is actually the special case, in which the constant *s* equals 1, of the following theorem. Theorem B.6****Suppose that a complexity function *T* (*n*) is eventually nondecreasing and satisfies  where *s* is a constant that is a power of *b*, *b* ≥ 2 and *k* ≥ 0 are constant integers, and *a*, *c*, and *d* are constants such that *a* > 0, *c* > 0, and *d* ≥0. Then the results in [Theorem B.5](#ap-bex31) still hold. **** Example B.28****Suppose that *T* (*n*) is eventually nondecreasing and satisfies  By [Theorem B.6](#ap-bex34), because 8 = 23,  **** This concludes our discussion of techniques for solving recurrences. Another technique is to use "generating functions" to solve recurrences. This technique is discussed in Sahni (1988). Bentley, Haken, and Sax (1980) provide a general method for solving recurrences arising from the analysis of divide-and-conquer algorithms ([see Chapter 2](LiB0014.html#141)).