# Improved Master Theorems for Divide-and-Conquer Recurrences.

Abstract. This paper presents new theorems to analyze divide-and-conquer recurrences, which improve other similar ones in several aspects. In particular, these theorems provide more information, free us almost completely from technicalities like floors and ceilings, and cover a wider set of toll functions and weight distributions, stochastic recurrences included.Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]; G.2.1 [Discrete Mathematics]: Combinatorics--recurrences and difference equations

General Terms: Algorithms, Measurement, Performance

Additional Key Words and Phrases: Asymptotic analysis, divide-and-conquer, master theorem

1. Introduction

This work presents new theorems to solve many divide-and-conquer recurrences that arise in practice. Recall that a recurrence is a definition of a function [F.sub.n] in terms of the values of F at indices smaller than n; a recurrence is divide-and-conquer--DAC, for short--if the average size of these indices is a fraction of n. Our reference source here is the Master Theorem--MT, for short--as it can be found in Sedgewick and Flajolet [1996]. Other references in this subject include the (classic) Master Theorem [Aho et al. 1974; Bentley et al. 1980; Cormen et al. 1990], several improvements [Kao 1997; Verma 1994; 1997; Wang and Fu 1996] as well as other related results [Karp 1994].

Assume that we have the recurrence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], with [t.sub.n] [is greater than] 0 and [S.sub.n] = Z [multiplied by] n + ??(1) for some 0 [is less than] Z [is less than] 1. If [F.sub.n] describes the cost to solve with a certain algorithm a problem of size n, then [t.sub.n]--customarily called toll function--is the cost of the divide and combine steps, W is the fixed number of recursive calls at each step, and [S.sub.n] is the size of the subproblems to be recursively solved. Let [Alpha] = -[log.sub.z] W. Then, the MT states that the solution to the recurrence is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](1).

(To be completely rigorous, the last case above requires additional conditions of smoothness for the toll function [t.sub.n].)

Usually, a MT does not provide an explicit solution but partial information about the function under study, like bounds on its growing order. Nevertheless, a MT has two interesting properties: First, it typically provides results which rely exclusively upon the asymptotic behaviour of the toll function and of the distribution of weights; for instance, in the MT above we only use the main term of [t.sub.n] and the value [Alpha], which depends on W and Z. In particular, this means that the values of [F.sub.n] at small indices are irrelevant to most MTs. Second, a MT is easy and fast to use. As an example, we can solve the DAC recurrence

(1) [M.sub.n] = n - 1 + [M.sub.??n/2??] + [M.sub.??n/2??]

for n [is greater than or equal to] 2, with [M.sub.0] = [M.sub.1] = 0, which defines the number of comparisons to sort an array of n keys with mergesort in the worst case [Flajolet and Golin 1994]. The term ??(1) in the definition of [S.sub.n] covers expressions with floors and ceilings in the argument of the recursive call. Hence, a direct application of the rules above yields [M.sub.n] = [Theta] (n log n).

In this paper, we will make the MT more flexible and more informative. For instance, consider the recurrence

(2) [B.sub.n] = 1 + ??(n - 1)/2??/n [multiplied by] [B.sub.??(n-1)/2??] + ??(n - 1)/2??/n [multiplied by] [B.sub.??(n-1)/2??]

for n [is greater than or equal to] 2, with [B.sub.0] = 0 and [B.sub.1] = 1, which defines the expected number of steps of a binary search for a random key in an array of size n. This recurrence does not follow the MT pattern utterly, since we have 1 - 1/n expected recursive calls at each step. Therefore, to use the MT we must assume that the solution to the recurrence [F.sub.n] = 1 + [F.sub.n/2] must be close to [B.sub.n]--which is true--, and conclude [B.sub.n] = [Theta](log n). We need a posterior reasoning to rigorously prove that this approximation does not lead to a wrong answer.

By contrast, the MT presented in Section 2 directly deals with recurrences where the number of recursive calls is not constant but tends to a constant. As a consequence, we will get rid of the annoying technicalities related to factors with floors and ceilings. And we will see that in some cases it is possible to get the multiplying factor of the dominating term of the function under study. This improvements will yield the result [B.sub.n] = [log.sub.2] n + o(log n) for the example above.

Yet we will extend the MT further, to deal with recurrences where the asymptotic sizes of the subproblems to be recursively solved consist in several fixed fractions of the original problem,(2) like

(3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for n large enough. (Since all the theorems in this work rely only upon the asymptotic properties of the toll function and the distribution of weights, we can avoid explicitly stating the initial values of the recurrence.)

It is frequent that the analysis of the cost of a given algorithm or data structure results in a stochastic recurrence, which does not follow any of the patterns mentioned above. As an example of stochastic recurrence, consider

(4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for n [is greater than or equal to] 1, with [Q.sub.0] = 0. This recurrence defines the expected number of comparisons to sort an n-key random array with quicksort. Clearly, the MTs we know so far cannot solve it, since the size of the subarrays to be recursively sorted is not fixed; it can be either an insignificant part of the whole input or almost it all. In this case, though, other techniques lead us to a closed solution [Hoare 1962].

Much more difficulties presents the analysis of the stochastic recurrence

(5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for n [is greater than or equal to] 1, with [Q.sub.0] = 0, where [Q.sub.n] denotes the expected number of comparisons during a half-defined search in a random quad-tree of size n. An accurate asymptotic expression for [Q.sub.n] can be obtained after a thorough analysis by means of generating functions [Flajolet et al. 1993], but this technique requires a deep knowledge and expertise.

Section 3 presents a new MT for stochastic recurrences, which shares the good properties of the MT in Section 2: it is simple and fast to use, and only the main term of [t.sub.n] and information on the asymptotic distribution of weights will be relevant. In addition, we will see how a simple iteration of the former MT sometimes yields several of the main terms of the function under study with their corresponding multiplicative factors.

The rest of the paper is organized as follows: Sections 4 and 5 present general-purpose theorems that solve many DAC recurrences that do not have to follow any particular pattern. Those theorems will allow us to prove in Sections 6 and 7 the MTs given in Sections 2 and 3, but also have other applications. For instance, they are useful for the analysis and asymptotic improvement of quicksort and quickselect [Martinez and Roura 1998].

In Section 8, we will see that it is possible to directly compute the main term of the variance of the cost of some algorithms, if the nonrecursive cost is large enough and the algorithm follows one of two typical patterns (quickselect and quicksort are prototypical examples of those patterns).

Finally, Section 9 presents some open problems.

Preliminary versions of this work appeared in Roura [1997a; 1997b].

2. The Discrete Master Theorem

In this section, we cast in the form of a Master Theorem some of the results that will be proved in latter sections. This MT deals with recurrences like (1), (2), and (3), where the problem is broken into pieces such that the asymptotic size of each one is a fixed fraction of the size of the whole problem. We call them discrete recursive definitions.

Definition 2.1. We say that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a discrete recursive definition of [F.sub.n] iff D [is greater than or equal to] 1; [R.sub.d,n] = [w.sub.d] + [r.sub.d,n] [is greater than or equal to] O, where [w.sub.d] [is greater than] 0 and [[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] |[r.sub.d,n]| = O([n.sup.-[Rho]]) for some [Rho] [is greater than] 0; and [S.sub.d,n] = [z.sub.d] [multiplied by] n + [s.sub.d,n], where 0 [is less than] [z.sub.d] [is less than] 1 and [[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] |[s.sub.d,n]| = O ([n.sup.-[Sigma]]) for some [Sigma] [is greater than] 0.

Here, D is the finite number of subproblems to be recursively solved; [R.sub.d,n] is the number of recursive calls to deal with the dth subproblem, where [w.sub.d] is the asymptotic number of calls to it; and [S.sub.d,n] is the (integer) size of the dth subproblem, where [z.sub.d] is the asymptotic fraction of the original problem to be solved by the dth recursive call.

For example, (1) is a discrete recursive definition. There we have two subproblems to recursively deal with: D = 2; whose size is asymptotically 1/2 of the size of the original problem: [z.sub.1] = [z.sub.2] = 1/2, -1 [is less than or equal to] [s.sub.1,n] [is less than or equal to] 0, 0 [is less than or equal to] [s.sub.2,n] [is less than or equal to] 1; and there is exactly one call to each one: [w.sub.1] = [w.sub.2] = 1, [r.sub.1,n] = [r.sub.2,n] = 0. For the bounds of [s.sub.n,k], we have used the fact that r - 1 [is less than or equal to] ??r?? [is less than or equal to] r and r [is less than or equal to] ??r?? [is less than or equal to] r + 1 for every real r. Notice that [Rho] = [Sigma] = 1 is a possible choice in this example.

The Discrete MT (Theorem 2.3) covers the presence of sublogarithmical factors in the toll function, that is, factors whose growing order is smaller than [log.sup.[Epsilon]] n for any [Epsilon] [is greater than] 0. This allows us to deal with toll functions like [t.sub.n] = [n.sup.2] [ln.sup.3] n [multiplied by] ln ln n, for instance. We define precisely this concept.

Definition 2.2. Let [[Mu].sub.n] be a strictly positive nondecreasing function for large n. Moreover, assume that for every [Epsilon] [is greater than] 0 the function [log.sup.[Epsilon]] n/[[Mu].sub.n] is increasing as long as n is large enough. Then we say that [[Mu].sub.n] is a sublogarithmical function.

Now we are ready to state the Discrete MT (examples of its use can be found in Appendix A).

THEOREM 2.3 (DISCRETE MASTER THEOREM). Let [F.sub.n] be a function defined by a discrete recursive definition, and let B [n.sup.a] [ln.sup.c] n [multiplied by] [[Xi].sub.n] be the main term of [t.sub.n], where B [is greater than] 0, a and c are arbitrary constants, and [[Xi].sub.n] = [[Mu].sub.n] or [[Xi].sub.n] = 1/[[Mu].sub.n] for some sublogarithmical function [[Mu].sub.n]. Let [Phi](x) = [[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] [w.sub.d] [multiplied by] [([z.sub.d]).sup.x], and H = 1 - [Phi](a). Then,

(1) if H [is greater than] 0, then [F.sub.n] ~ [t.sub.n]/H;

(2) if H = 0, then

(2.1) if c [is greater than] -1, then [F.sub.n] ~ [t.sub.n] ln n/H', where H' = -(c + 1)[[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] [W.sub.d] [multiplied by] [([z.sub.d]).sup.a] ln [z.sub.d];

(2.2) if c = - 1, then [F.sub.n] = ??([n.sup.a] [log.sup.[Epsilon]] n) for any [Epsilon] [is greater than] 0, and [F.sub.n] = [Omega]([n.sup.a]) if [F.sub.n] [is greater than or equal to] 0 for every n [is greater than or equal to] 0;

(2.2') if c = -1 and [[Mu].sub.n] = 1, then [F.sub.n] ~ [t.sub.n] ln n [multiplied by] ln ln n/H", where H" = -[[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] [w.sub.d] [multiplied by] [([z.sub.d]).sup.a] ln [z.sub.d];

(2.3) if C [is less than] -1, then [F.sub.n] = ??([n.sup.a]) ([F.sub.n] = [Theta]([n.sup.a]), if [F.sub.n] [is greater than or equal to] 0 for every n [is greater than or equal to] 0);

(3) if H [is less than] 0, then [F.sub.n] = ??([n.sup.[Alpha]]) ([F.sub.n] = [Theta]([n.sup.[Alpha]]), if [F.sub.n] [is greater than or equal to] 0 for every n [is greater than or equal to] 0), where [Alpha] is the unique solution of [Phi]([Alpha]) = 1.

PROOF. Section 6 is devoted to prove this theorem. []

The Discrete MT could be trivially adapted to deal with negative toll functions by changing the conditions "B [is greater than] 0" and "[F.sub.n] [is greater than or equal to] 0 for every n [is greater than or equal to] 0" to "B [is less than] 0" and "[F.sub.n] [is less than or equal to] 0 for every n [is greater than or equal to] 0", respectively.

Also, though we will not prove it in this work, we could relax Definition 2.1 to permit the value [z.sub.d] = 1 for some indices, as long as (a) there is, at least, one index d such that 0 [is less than] [z.sub.d] [is less than] 1; and (b) the total sum of weights [w.sub.d] of the indices d with [z.sub.d] = 1 is strictly smaller than 1. Notice that neither

(6) [A.sub.n] = [t.sub.n] + [A.sub.n-3]

nor

(7) [B.sub.n] = [t.sub.n] + [2B.sub.??n/2??] + [2B.sub.n-1]

is, even under the relaxation above, a discrete recursive definition. The first recurrence does not satisfy any of the two conditions, while the second recurrence fails to fulfill the condition (b). They are out of the scope of this paper. By contrast, the recurrence

[F.sub.n] = [t.sub.n] + [F.sub.??n/2??] + 1/2 [multiplied by] [F.sub.n-2]

is a discrete recursive definition, and so we could analyze it exactly as stated by the Discrete MT.

The case [z.sub.d] = 0 for some indices 1 [is less than or equal to] d [is less than or equal to] D is especially awkward. We avoid dealing with it.

3. The Continuous Master Theorem

This section covers the analysis of recurrences like (4) and (5), which we will call continuous. But first we need to define the concept of shape function (the reason for this name will be clear after Definition 3.2).

Definition 3.1. Let [Omega] (z) [is greater than or equal to] 0 be a function over [0, 1] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] exists and is at least 1. Furthermore, assume that there is some [Mu] [is less than] 0 such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] also converges.(3) Then we say that [Omega](z) is a shape function.

Definition 3.2. We say that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a continuous recursive definition of [F.sub.n] iff there exist some shape function [Omega](z), some constant 0 [is less than] q [is less than or equal to] 1 and some function [M.sub.n] = [Theta]([n.sup.q]) with integer values such that, if we define [z.sub.n,j] = j/[M.sub.n] for every 0 [is less than or equal to] j [is less than or equal to] [M.sub.n], [I.sub.n,j] = [[z.sub.n,j] [multiplied by] n, [z.sub.n,j + 1] [multiplied by] n) for every 0 [is less than or equal to] j [is less than] [M.sub.n], and

(8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for every 0 [is less than or equal to] j [is less than] [M.sub.n], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [Rho] [is greater than] 0.

Usually, [M.sub.n] = n is a possible choice, and in this case (8) reduces to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Loosely speaking, we can use the integral in the expression above to find a good approximation to [[Omega].sub.n,k]. Notice that there can only be one shape function [Omega](z) related to a given continuous recursive definition, except for bizarre shape functions obtained from [Omega](z) by changing its value at a finite number of points, or by similar minor perturbations.

For instance, consider the recurrence

(9) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for the expected number of comparisons to select the ith out of n keys using quickselect--also known as FIND [Hoare 1961]--when i is chosen at random. Its shape function is [Omega](z) = 2z (see Figure 1), since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and hence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with [Rho] = 1.

Therefore, [Omega](z) is nothing except the asymptotic shape of the distribution of weights, which now is very similar to a continuous probability distribution, where the area beneath the function is the asymptotic number of recursive calls. Since, by definition, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we are assuming that there is at least one recursive call for large n. This condition (very likely to hold in practice) simplifies the study of these recurrences.

On the other hand, we have allowed [M.sub.n] to be [Theta]([n.sup.q]) for some q [is less than or equal to] 1, as long as q [is greater than] 0. So it is not necessary that [Omega](z) fits the n weights individually, but a polynomial number of groups of weights. This relaxation could be useful when dealing with particularly difficult recurrences.

THEOREM 3.3 (CONTINUOUS MASTER THEOREM). Let [F.sub.n] be a function defined by a continuous recursive definition, and let B [n.sup.a] [ln.sup.c] n [multiplied by] [[Xi].sub.n] be the main term of [t.sub.n], where B [is greater than] 0, a and c are arbitrary constants, and [[Xi].sub.n] = [[Mu].sub.n] or [[Xi].sub.n] = 1/[[Mu].sub.n] for some sublogarithmical function [Mu].sub.n]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and H = 1 - [Psi](a). Then,

(1) if H [is greater than] 0, then [F.sub.n] ~ [t.sub.n]/H;

(2) if H = 0, then

(2.1) if c [is greater than] -1, then [F.sub.n] ~ [t.sub.n] ln n/H', where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(2.2) if c = -1, then [F.sub.n] = ?? ([n.sup.a] [log.sup.[Epsilon]] n) for any [Epsilon] [is greater than] 0, and [F.sub.n] = [Omega]([n.sup.a]) if [F.sub.n] [is greater than or equal to] 0 for every n [is greater than or equal to] 0;

(2.2') if c = -1 and [[Mu].sub.n] = 1, then [F.sub.n] ~ [t.sub.n] ln n [multiplied by] ln ln n/H", where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(2.3) if c [is less than] -1, then [F.sub.n] = ??([n.sup.a]) ([F.sub.n] = [Theta]([n.sup.a]), if [F.sub.n] [is greater than or equal to] 0 for every n [is greater than or equal to] 0);

(3) if H [is less than] 0 (including the case H = -[infinity]) then [F.sub.n] = ??([n.sup.[Alpha]]) ([F.sub.n] = [Theta]([n.sup.[Alpha]]), if [F.sub.n] [is greater than or equal to] 0 for every n [is greater than or equal to] 0), where [Alpha] is the unique solution of [Psi]([Alpha]) = 1.

PROOF. Section 7 is devoted to prove this theorem. []

To use the Continuous Master Theorem, we must first identify the shape function [Omega](z) for the distribution of weights. This is equivalent to identifying the values [{[w.sub.d]}.sub.1 [is less than or equal to] d [is less than or equal to] D] and [{[z.sub.d]}.sub.1 [is less than or equal to] d [is less than or equal to] D] for the discrete case. One possibility is to conjecture that [Omega](z) = n [multiplied by] [[Omega].sub.n,zn]. For instance, for (9) this technique yields [Omega](z) = n [multiplied by] 2/[n.sup.2] [multiplied by] zn = 2z, which we have already proved to be right. But for (5) we have additional problems, since the expression n [multiplied by] [[Omega].sub.n,zn] = 4(1 - z)/(1 + 1/n) includes n. Lemma 7.2 in Section 7 provides a way to find [Omega](z) that works in many practical situations.

Examples of how to use the Continuous Master Theorem can be found in Appendix B.

4. The Core Theorems

In this section and Section 5, we will prove some general theorems that apply to many DAC recurrences. In Sections 6 and 7, we will see how to use these results to prove the statements of both the Discrete and the Continuous MTs.

We begin introducing the concept of divide-and-conquer recursive definition formally.

Definition 4.1. Let [F.sub.n] be a function defined for every n [is greater than or equal to] 0, and let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

be a recursive definition, with N [is greater than or equal to] 1 and [w.sub.n,k] [is greater than or equal to] 0. For every n [is greater than or equal to] N, let [W.sub.n] = [[Sigma].sub.0 [is less than or equal to] k [is less than] n] [w.sub.n,k] and [Z.sub n] = [[Sigma].sub.0 [is less than or equal to] k [is less than] n] ([w.sub.n, k]/[W.sub.n]) (k/n) Then we say that F is a DAC recursive definition of [F.sub.n] if and only if (a) [F.sub.n] = [b.sub.n] for every 0 [is less than or equal to] n [is less than] N; (b) for every n [is greater than or equal to] N,

(10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and (c) it exists some upper bound U [is less than] 1 such that [Z.sub.n] [is less than or equal to] U for all n large enough. We also define W = [lim.sub.n [right arrow] [infinity]] [W.sub.n] and Z = [lim.sub.n [right arrow] [infinity]] [Z.sub.n], if they exist.

This definition can be easily interpreted: [W.sub.n] is the total number of recursive calls to solve a problem of size n; [Z.sub.n] is the average fraction of the original problem that is solved by a recursive call (it turns out that 0 [is less than or equal to] [Z.sub.n] [is less than] 1); and for large n, the average size of the recursive calls is, at most, a fraction of the whole problem. For example, for (9), we have [W.sub.n] = 1 - 1/n, W = 1, [Z.sub.n] = 2/3 - 1/3n and Z = 2/3, while for (1) we have [W.sub.n] = 2, W = 2, [Z.sub.n] = 1/2 and Z = 1/2. By contrast, (6) is not a DAC recursive definition.

Most of the results from which both MTs are derived refer to canonical recursive definitions, which are defined as follows:

Definition 4.2. Let F be a DAC recursive definition of a function [F.sub.n]. We say that F is a canonical recursive definition if and only if both these properties hold: (a) The constant W exists and is equal to 1. (b) If we define [m.sub.n] = [W.sub.n] - W, then |[m.sub.n]| = ??([n.sup.-[Rho]]) for some [Rho] [is greater than] 0.

Hence, a DAC recursive definition is canonical if the number of recursive calls tends to 1, with a minimum convergence speed. For instance, for (9), we have W = 1, and |[m.sub.n]| = 1/n = ??([n.sup.-[Rho]) with [Rho] = 1.

Now, assume that [F.sub.n] [is greater than or equal to] 0 is defined by (10). Then we have [F.sub.n] = [Omega]([t.sub.n]), because [F.sub.n] cannot grow more slowly than [t.sub.n] does. So the question is identifying under which conditions [F.sub.n] can grow faster than [t.sub.n]. For the recursive definitions we deal with and roughly speaking, we will prove that there is a growing order [Theta]([n.sup.[Alpha]]) associated to every distribution of weights, irrespectively of how small [t.sub.n] is. This would be similar to state that [F.sub.n] = [Theta](max{[t.sub.n], [n.sup.[Alpha]]}), which is almost true.

For instance, consider the recurrence

(11) [F.sub.n] = [t.sub.n] + [F.sub.??n/4??].

We will see in this section that [Alpha] = 0 for any canonical recurrence, such as this one. Therefore, for "large" values of [t.sub.n] (case 1 of the MTs) like n, [n.sup.3] or even [2.sup.n], we should get [F.sub.n] = [Theta]([t.sub.n]), which is true. For "small" values of [t.sub.n] (case 3 of the MTs) like 1/n, 1/[n.sup.3] or [2.sup.-n], [F.sub.n] should be [Theta](1), which is also true. However, things are not so easy for values of [t.sub.n] close to [Theta](1) (case 2 of the MTs). For example, for [t.sub.n] = 1 the growing order of [F.sub.n] turns out to be [Theta](log n) instead of [Theta](1). We will see in Section 5 why this additional factor appears.

At this point, it is worth commenting on the word "Core" in the title of this section. It tries to suggest the idea that recursive definitions with a toll function small enough--and thus inside the zone dominated by the term [Theta]([n.sup.[Alpha]]) associated to the distribution of weights--are the most difficult to analyze. Indeed, there is no way to find the lower order terms of [F.sub.n] nor even the multiplicative factor of the main term [n.sup.[Alpha]], but to consider all the values of [F.sub.n] the values at small indices included.

For example, consider (11), and assume that it holds for n [is greater than or equal to] 1. Let [t.sub.n] [is greater than] 0 be small enough. Then [F.sub.n] = [Theta](1), but modifying [F.sub.0] yields a significant change in [F.sub.n] for every n. In fact, changing the value of the function at any index significantly affects F at an infinite number of indices. Set in terms of a recursion tree (see Cormen et al. [1990], for example), the solution to the recurrence is dominated by the values at the leaves.

Moreover, in some cases, the multiplicative factor of the main term [n.sup.[Alpha]] is not even asymptotically constant. Consider the following recurrence,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for every n [is greater than or equal to] 2. Let [t.sub.n] [is greater than] 0 be small enough and such that [t.sub.2n] = [t.sub.2n+1], and let [F.sub.0] = 0 and [F.sub.1] = 1. Then it is easy to see that [F.sub.n] = [Theta](1), but [F.sub.n] cannot tend to a constant, since it fluctuates periodically.

We end this section with two theorems which formalize one of the claims above, namely that any canonical recurrence is on the one hand [Omega](1), and on the other hand ??(1) for [t.sub.n] small enough. The three technical conditions in the statement of Theorem 4.3 typically hold and, loosely speaking, avoid cases like "everything is zero" and "the negative and the positive contributions cancel out."

THEOREM 4.3. Let [F.sub.n] be defined by a canonical recursive definition, and let [b.sub.n] [is greater than or equal to] 0, [t.sub.n] [is greater than] 0 and [[Sigma].sub.0 [is less than or equal to] k [is less than] N] [w.sub.n,k] = ??([n.sup.-[Sigma]]) for some [Sigma] [is greater than] 0. Then [F.sub.n] = [Omega](1).

PROOF. By hypothesis, |[m.sub.n]| = |[W.sub.n] - 1| = ??([n.sup.-[Rho]]), where [Rho] [is greater than] 0. Choose some v such that 0 [is less than] v [is less than] max{[Rho], [Sigma]}, and define [W'.sub.n] = [[Sigma].sub.N [is less than or equal to] k [is less than] n] [w.sub.n, k]. Taking into account that [W.sub.n] [is greater than or equal to] 1 - |[m.sub.n]|, we have [W'.sub.n] = [W.sub.n] - [[Sigma].sub.0 [is less than or equal to] k [is less than] N] [w.sub.n, k] [is greater than or equal to] 1 + ??([n.sup.-[Rho]]) - ??([n.sup.-[Sigma]]) [is greater than or equal to] 1 - [n.sup.-v], as long as n is large enough.

Now define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where 0 [is less than] U [is less than] 1 is the upper bound for the [Z.sub.n]'s that exists by definition. Choose any V such that U [is less than] V [is less than] 1. Then it is clear that [Z'.sub.n] [is less than or equal to] V for large n.

For the next step of the proof, choose some N' [is greater than] N large enough to get [W'.sub.n] [is greater than or equal to] 1 - [n.sup.-v], [Z'.sub.n] [is less than or equal to] V, and also [n.sup.-v] [is less than or equal to] 1/2 for every n [is greater than or equal to] N'. Let h(x) = exp([2V.sup.v]/(1 - [V.sup.v])[x.sup.v]). In what follows, we will use the easy-to-prove fact that h(x) [is greater than or equal to] 1 is a decreasing convex function in the interval [1, +[infinity]).

Set M = min[{[F.sub.n]/h(n)}.sub.N [is less than or equal to] n [is less than] N']. Notice that [b.sub.n] [is greater than or equal to] 0 and [t.sub.n] [is greater than] 0 imply M [is greater than] 0. We can prove by induction that [F.sub.n] [is greater than or equal to] M [multiplied by] h(n) holds not only for all N [is less than or equal to] n [is less than] N' but also for all n [is greater than or equal to] N': Assuming the induction hypothesis, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The convexity of h(x), the bound for [W'.sub.n] and the fact that h(x) is decreasing yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From the definition of [Z'.sub.n], [F.sub.n] [is greater than or equal to] M(1 - [n.sup.-v]) [multiplied by] h(n[Z].sub.n]). Taking into account that 1 - x [is greater than or equal to] exp(-2x) for all 0 [is less than or equal to] x [is less than or equal to] 1/2, and replacing x by [n.sup.-v], we get 1 - [n.sup.-v] [is greater than or equal to] exp(-[2n.sup.-v]). Furthermore, [Z'.sub.n] [is less than or equal to] V and h(x) is decreasing, and thus we have [F.sub.n] [is greater than or equal to] M exp(-[2n.sup.-v]) [multiplied by] h (nV) = M [multiplied by] h (n), the last step obtained through simple manipulations. This ends the inductive proof.

Finally, h(n) [is greater than or equal to] 1 yields [F.sub.n] [is greater than or equal to] M [is greater than] 0 for every n [is greater than or equal to] N, and the statement of the theorem follows. []

THEOREM 4.4. Let [F.sub.n] be defined by a canonical recursive definition, and let [t.sub.n] = ??([log.sup.c] n) for some c [is less than] -1. Then [F.sub.n] = ??(1).

PROOF. Let F be the recursive definition for [F.sub.n]. First of all, we introduce a recursive definition G for a new function [G.sub.n], by modifying F as follows: Let [[Sigma].sub.n,k] denote the weights of F, [Y.sub.n] denote [[Sigma].sub.0 [is less than or equal to] k [is less than] n] [[Sigma].sub.n,k], and assume without loss of generality that [Y.sub.n] [is greater than] O--recall that [lim.sub.n [right arrow] + [infinity]] [Y.sub.n] = 1. Define [w.sub.n,k], the weights of G, to be equal to [[Sigma].sub.n,k] if [Y.sub.n] [is greater than or equal to] 1, and equal to [[Sigma].sub.n,k]/[Y.sub.n] if [Y.sub.n] [is less than] 1 (this is just a normalization of the weights so that they sum at least 1). Let [u.sub.n] be the toll function of F; we define the toll function of G as [t.sub.n] = |[u.sub.n]|. Altogether, -[G.sub.n] [is less than or equal to] [F.sub.n] [is less than or equal to] [G.sub.n] trivially holds for every n [is greater than or equal to] 0, so it is enough to bound [G.sub.n] by above to prove the theorem.

Let [W.sub.n], W, etc. be as in Definitions 4.1 and 4.2 but for the set of weights [w.sub.n,k] of G. Then, on the one hand, we have that W is still 1, but now [W.sub.n] [is greater than or equal to] 1 and [m.sub.n] [is greater than or equal to] 0. On the other hand [Z.sub.n] remains the same and hence [Z.sub.n] [is less than or equal to] U for some 0 [is less than] U [is less than] 1. Choose some V such that U [is less than] V [is less than] 1, and some v such that 0 [is less than] v [is less than] [Rho], where [Rho] [is greater than] 0 is the constant in Definition 4.2. Choose some a [is greater than or equal to] 1 large enough to get [V.sup.v]/(1 - [V.sup.v]) [is less than or equal to] [a.sup.v]. We introduce two auxiliar functions, f(x) = exp(-[V.sup.v]/[(1 - [V.sup.v])(x + a).sup.v]), and g(x) = [[Sigma].sub.i [is greater than or equal to] 1] [g.sub.i][(x).sup.c] , where [g.sub.i](x) = ln(x + a) - i ln V. It is not difficult to prove that, for every x [is greater than or equal to] 0, 0 [is less than] f(x) [is less than or equal to] 1 is an increasing concave function, and g(x) [is greater than or equal to] 0 is a well-defined decreasing convex function.

There are three bounds for the quantities introduced so far that we will find helpful through this proof (they all hold for n large enough, say for n [is greater than or equal to] N' for some constant N'). First, taking into account that [m.sub.n] = ??([n.sup.-[Rho]]), we have 0 [is less than or equal to] [m.sub.n] [is less than or equal to] 1/([(n + a).sup.v] + 1). Second, we define [Z'.sub.n] = (n[Z.sub.n] + a)/(n + a) = [Z.sub.n] + a(1 - [Z.sub.n])/(n + a) [is less than or equal to] U + a/n [is less than or equal to] V. Finally, by the initial hypothesis about [t.sub.n] we know that there exists some constant K [is greater than] 0 such that [t.sub.n] [is less than or equal to] K [ln.sup.c](n + a).

Assume n [is greater than or equal to] N' and introduce

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where for the second equality above we have used the fact that [W.sub.n] = 1 + [m.sub.n]. Then, since f(x) is positive, increasing and concave, and [m.sub.n] is positive, we can bound [S.sub.n] to get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By the definition of [Z'.sub.n], we know that n[Z.sub.n] + a = (n + a)[Z'.sub.n] [is less than or equal to] (n + a)V. Therefore,

(12) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For the next step we use an auxiliar function [A.sub.n] = 1 - 1/([(n + a).sup.v] + 1) = [(n + a).sup.v]/([(n + a).sup.v] + 1). Since 1/[A.sub.n] = 1 + 1/[(n + a).sup.v], and 1 + x [is less than or equal to] exp(x) for every x [is greater than or equal to] 0, it follows that 1/[A.sub.n] [is less than or equal to] exp(1/[(n + a).sup.v]), and thus [A.sub.n] [is greater than or equal to] exp(-1/[(n + a).sup.v]). Hence, [A.sub.n]f(n) [is greater than or equal to] exp(-1/[(n + a).sup.v])f(n) = exp(-(1 - [V.sup.v])/[(n + a).sup.v]), and from (12), [m.sub.n] [is less than or equal to] 1/([(n + a).sup.v] + 1), and the definition of [A.sub.n] we conclude [S.sub.n] [is less than or equal to] f(n). We will use this inequality in a moment.

Now introduce [R.sub.n] = [[Sigma].sub.0 [is less than or equal to] k [is less than] n] [w.sub.n,k], and use the convexity of g(x) to get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By definition, [g.sub.i](n[Z.sub.n]) = ln(n[Z.sub.n] + a) - i ln V = ln((n + a)[Z'.sub.n]) - i ln V. Assume n [is greater than or equal to] N'; the bound for [Z'.sub.n] yields [g.sub.i](n[Z.sub.n]) [is less than or equal to] ln(n + a) + ln V - i ln V = [g.sub.i-1](n). Therefore, [R.sub.n] [is greater than or equal to] [[Sigma].sub.i [is greater than or equal to] 1] [g.sub.i - 1][(n).sup.c] = [ln.sup.c](n + a) + g(n).

We are ready to prove the theorem. Set M = max[{([G.sub.n]/K + g(n))/ f(n)}.sub.0 [is less than or equal to] n [is less than] N']. Then we have [G.sub.n]/K [is less than or equal to] M [multiplied by] f(n) - g(n) for any n [is less than] N'. We can prove this bound by induction when n [is greater than or equal to] N':

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Finally, we have [F.sub.n] [is less than or equal to] [G.sub.n] [is less than or equal to] K(M [multiplied by] f(n) - g(n)) [is less than or equal to] K [multiplied by] M for every n [is greater than or equal to] 0 (and [F.sub.n] [is greater than or equal to] -K [multiplied by] M), and the theorem is proved. []

5. The Flesh Theorems

In this section, we deal with the canonical recursive definitions whose toll function is large enough to dominate the solution. These recurrences are typically easier to analyze than those in Section 4 (and thus the "Flesh" in the title), and in most cases we can get the multiplicative factor of the main term of the function under study. Moreover, sometimes it is possible to extract one by one several main terms with their multiplicative factors, until the core is reached (see Appendix B).

The reason for the name chosen in the following definition will be clear after Theorem 5.3.

Definition 5.1. Let [u.sub.n] be a function over the integers. We say that [[Gamma].sub.n] is a bounding function of [u.sub.n] if and only if there exist some constant [N.sub.[Gamma]] [is greater than or equal to] 1 and some strictly positive nonincreasing function [Beta](z) defined over (0, 1) such that (a) [u.sub.n][[Gamma].sub.n] - [u.sub.k][[Gamma].sub.k] [is greater than or equal to] [Beta](k/n)[u.sub.n] for every n [is less than] [N.sub.[Gamma]] and every [N.sub.[Gamma]] [is less than or equal to] k [is less than] n; (b) [u.sub.n], [[Gamma].sub.n] [is greater than] 0 for every n [is greater than or equal to] [N.sub.[Gamma]]; (c) [[Gamma].sub.n] is a subpolynomial function; and (d) [u.sub.n][[Gamma].sub.n] = [Omega](1).

For instance, [[Gamma].sub.n] = 1 is a bounding function of [u.sub.n] = [n.sup.2]. Take [Beta](z) = 1 - [z.sup.2]. Then we have [u.sub.n][[Gamma].sub.n] = [u.sub.k][[Gamma].sub.k] = [n.sup.2] - [k.sup.2] = (1 - [(k/n).sup.2])[n.sup.2] = [Beta](k/n)[u.sub.n]. The other conditions trivially hold.

The word "entropy" is defined below with a meaning wider than usually. Our definition reduces to the traditional one when [t.sub.n] = 1 and [[Gamma].sub.n] = [log.sub.2] n.

Definition 5.2. Let F be a canonical recursive definition of a function [F.sub.n], and let [[Gamma].sub.n] be a bounding function of [t.sub.n]. We define the entropy of F with respect to [[Gamma].sub.n] at every n [is greater than or equal to] max{N, [N.sub.[Gamma]]} as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We also define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], if it exists.

The next theorem, together with Lemma 5.4, will allow us to bound the solution of many canonical recursive definitions.

THEOREM 5.3. Let [F.sub.n] be defined by a canonical recursive definition, and let [[Gamma].sub.n] be a bounding function of [u.sub.n]. If [t.sub.n] = ??([u.sub.n]), then [F.sub.n] = ??([u.sub.n][[Gamma].sub.n]). If [t.sub.n] = o([u.sub.n]), then [F.sub.n] = o([u.sub.n][[Gamma].sub.n]).

PROOF. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be defined as in (13) but using [u.sub.n] instead of [t.sub.n]. We first prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], as follows. We know that [Z.sub.n] [is less than or equal to] U for large n, where 0 [is less than] U [is less than] 1. Choose some V such that U [is less than] V [is less than] 1, and let n be large enough to get nV [is greater than] [N.sub.[Gamma]]. Then [t.sub.n][[Gamma].sub.n] [is greater than] [t.sub.n][[Gamma].sub.n] - [t.sub.k][[Gamma].sub.k] [is greater than or equal to] [Beta](k/n)[t.sub.n] [is greater than or equal to] [Beta](V)[t.sub.n] for every [N.sub.[Gamma]] [is less than or equal to] k [is less than] nV. Alternatively, we can write [[Gamma].sub.n] [is greater than] [[Gamma].sub.n] - [t.sub.k]/[t.sub.n] [multiplied by] [[Gamma].sub.k] [is greater than or equal to] [Beta](V). We now use these bounds in the definition of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

On the other hand, from

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

we have [[Sigma].sub.0 [is less than or equal to] k [is less than] nV] [w.sub.n,k] = [W.sub.n] - [[Sigma].sub.nV [is less than or equal to] k [is less than] n] [w.sub.n,k] [is greater than or equal to] (1 - U/V)[W.sub.n]. Altogether, we deduce [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. But [m.sub.n][[Gamma].sub.n] vanishes for large n, because |[m.sub.n]| = ??([n.sup.-[Rho]]) for some [Rho] [is greater than] 0 and [[Gamma].sub.n] is a subpolynomial function. Therefore, since 1 - U/V [is greater than] 0, [Beta](V) [is greater than] 0 and [W.sub.n] tends to W = 1, we have [H.sub.n] [is greater than or equal to] Q for some constant Q [is greater than] 0 and n large enough (say, larger than some constant [N.sub.H]).

Now we can prove the ??() case. Since [t.sub.n] = ??([u.sub.n]), there exist constants K [is greater than] 0 and M such that |[t.sub.n]| [is less than or equal to] [Ku.sub.n] for every n [is greater than or equal to] M. Choose M to be at least [N.sub.H], and introduce a new function,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

A simple proof by induction yields -[G.sub.n] [is less than or equal to] [F.sub.n] [is less than or equal to] [G.sub.n] for every n. Now define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let n [is greater than or equal to] M. Using the definitions of [I.sub.n] and [G.sub.n] in the first step, and the definition of [I.sub.n] back in the second step, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From the bound for [H.sub.n], the toll function above is [is less than or equal to] [Ku.sub.n] - K/Q [multiplied by] [u.sub.n]Q = 0, as long as n [is greater than or equal to] M. Therefore, if we define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

then we have [I.sub.n] [is less than or equal to] [J.sub.n]. But according to Theorem 4.4, [J.sub.n] = ??(1), that is, [J.sub.n] [is less than or equal to] S for some constant S [is greater than] 0 and n large enough. This implies [I.sub.n] [is less than or equal to] S as well, and hence [F.sub.n] [is less than or equal to] [G.sub.n] = [I.sub.n] + K/Q [multiplied by] [u.sub.n][[Gamma].sub.n] [is less than or equal to] S + K/Q [multiplied by] [u.sub.n][[Gamma].sub.n] or alternatively, [F.sub.n]/[u.sub.n][[Gamma].sub.n] [is less than or equal to] S/[u.sub.n][[Gamma].sub.n] + K/Q. Taking into account that [u.sub.n][[Gamma].sub.n] = [Omega](1), the term S/[u.sub.n][[Gamma].sub.n] will vanish for large n, and thus we can conclude [F.sub.n]/[u.sub.n][[Gamma].sub.n] [is less than or equal to] K' (and [F.sub.n]/[u.sub.n][[Gamma].sub.n] [is greater than or equal to] -K') for any constant K' [is greater than] K/Q as long as n is large enough. The case ??() is proved.

The proof of the case o() follows the pattern above. Therefore, we only point out the differences. We have to show that for every [Epsilon] [is greater than] 0 there is some [N.sub.[Epsilon]] large enough such that |[F.sub.n]|/[u.sub.n][[Gammma].sub.n] [is less than or equal to] [Epsilon] as long as n [is greater than or equal to] [N.sub.[Epsilon]]. Set v = Q [multiplied by] [Epsilon]/2. Then, by hypothesis, it exists some [M.sub.v] such that |[t.sub.n]| [is less than or equal to] [vu.sub.n] for every n [is greater than or equal to] [M.sub.v]. Define [G.sub.n] using [vu.sub.n] as toll function for every n [is greater than or equal to] [M.sub.v], and [I.sub.n] as [G.sub.n] - v/Q [multiplied by] [u.sub.n][[Gamma].sub.n] for every n [is greater than or equal to] [N.sub.[Gamma]]. Then we have [I.sub.n] = [S.sub.v] for some constant [S.sub.v] [is greater than] 0 and every n large enough, and thus [F.sub.n]/[u.sub.n][[Gamma].sub.n] [is less than or equal to] [S.sub.v]/[u.sub.n][[Gamma].sub.n] + v/Q. Since the first term vanishes for large n, we can always pick some [N.sub.[Epsilon]] large enough to get [F.sub.n]/[u.sub.n][[Gamma].sub.n] [is less than or equal to] v/Q + v/Q = [Epsilon] for every n [is greater than or equal to] [N.sub.Epsilon]] (and also [F.sub.n]/[u.sub.n][[Gamma].sub.n] [is greater than or equal to] -[Epsilon]), thus proving the case o() and the theorem. []

The following lemma provides bounding functions for the most usual toll functions.

LEMMA 5.4

--Let [u.sub.n] =[n.sup.a][[Delta].sub.n] for every n [is greater than or equal to], [N.sub.u], where [N.sub.u] [is greater than or equal to] 1, a [is greater than] 0, and [[Delta].sub.n] is a strictly positive nondecreasing function at every n [is greater than or equal to] [N.sub.u]. Then [[Gamma].sub.n] = 1 is a bounding function of [u.sub.n].

--Let [v.sub.n] =[ln.sup.c] n [multiplied by] [[Epsilon].sub.n] for every n [is greater than or equal to] [N.sub.v], where [N.sub.v] [is greater than or equal to] 2, c [is greater than] -1, and [[Epsilon].sub.n] is a strictly positive nondecreasing function at every n [is greater than or equal to] [N.sub.v]. Then [[Gamma].sub.n]= ln n is a bounding function of [v.sub.n].

--Let [w.sub.n] = [ln.sup.-1] n for every n [is greater than or equal to] [N.sub.w], for some [N.sub.w] [is greater than or equal to] 3. Then [[Gamma].sub.n] = ln n [multiplied by] ln ln n is a bounding function of [w.sub.n].

PROOF. For the first case, let [N.sub.[Gamma]] = [N.sub.u] and take [Beta](z) = 1 - [z.sup.a]. Thus, [Beta](z) [is greater than] 0 is nonincreasing in (0, 1). Take any n [is greater than] [N.sub.[Gamma]] and any [N.sub.[Gamma]] [is less than or equal to] k [is less than] n. Then [u.sub.n][[Gamma].sub.n] - [u.sub.k][[Gamma].sub.k] = [n.sup.a][[Delta].sub.n] - [k.sup.a][[Delta].sub.k] [is greater than or equal to] [n.sup.a][[Delta].sub.n] - [k.sup.a][[Delta].sub.n] = (1 - [(k/n).sup.a])[n.sup.a][[Delta].sub.n] = [Beta](k/n)[u.sub.n], and the condition (a) in Definition 5.1 is satisfied. The conditions (b), (c), and (d) are trivial to prove.

For the second case, take [Beta](z) = -(c + 1)ln z, if -1 [is less than] c [is less than or equal to] 0, or [Beta](z) = -ln z, if c [is greater than] 0. Let [N.sub.[Gamma]] = [N.sub.v], and take any k and n such that [N.sub.[Gamma]] [is less than or equal to] k [is less than] n. For the moment, we have [v.sub.n][[Gamma].sub.n] - [v.sub.k][[Gamma].sub.k] = [ln.sup.c+1] n [multiplied by] [[Epsilon].sub.n] - [ln.sup.c+1] k [multiplied by] [[Epsilon].sub.k] [is greater than or equal to] [ln.sup.c+1] n [multiplied by] [[Epsilon].sub.n] - [ln.sup.c+1] k [multiplied by] [[Epsilon].sub.n] = ([ln.sup.c+1] n - [ln.sup.c+1] k)[[Epsilon].sub.n].

To check that the condition (a) in Definition 5.1 holds, we consider the last expression separately for positive and negative c. For c [is greater than] 0, it is not difficult to prove that [ln.sup.c+1] n - [ln.sup.c+1] k [is greater than or equal to] -ln(k/n)[ln.sup.c] n when n [is greater than or equal to] 1 and 1 [is less than or equal to] k [is less than or equal to] n. Therefore, [v.sub.n][[Gamma].sub.n] - [v.sub.k][[Gamma].sub.k] -ln(k/n)[ln.sup.c] n [[Epsilon].sub.n] = [Beta](k/n)[v.sub.n]. Similarly, when -1 [is less than] c [is less than or equal to] 0 it suffices to prove that [ln.sup.c+1] n - [ln.sup.c+1] k [is greater than or equal to] -(c + 1)ln(k/n) [ln.sup.c] n when n [is greater than or equal to] 1 and 1 [is less than or equal to] k [is less than or equal to] n, and then [v.sub.n][[Gamma].sub.n] - [v.sub.k][[Gamma].sub.k] [is greater than or equal to] -(c + 1)ln(k/n)[ln.sup.c] n [multiplied by] [[Epsilon].sub.n] = [Beta](k/n)[v.sub.n]. The rest of conditions in Definition 5.1 trivially hold.

For the third case, let [N.sub.[Gamma]] = [N.sub.w], and take any n [is greater than] [N.sub.[Gamma]] and any [N.sub.[Gamma]] [is less than or equal to] k [is less than] n. Define [Beta](z) = -ln z, and let y = ln n and z = k/n. It can be shown that ln y - ln(y + ln z) [is greater than or equal to] -ln z/y for all z in (exp(-y), 1]. Therefore, [w.sub.n][[Gamma].sub.n] - [w.sub.k][[Gamma].sub.k] = ln ln n - ln ln k = ln y - ln(y + ln z) [is greater than or equal to] -ln z/y = [Beta](k/n)[w.sub.n]. The rest of conditions for a bounding function can be easily proved. []

The following corollary is an immediate consequence of Theorem 5.3 and Lemma 5.4.

COROLLARY 5.5. Let the functions [F.sub.n], [G.sub.n], and [H.sub.n] be defined by canonical recursive definitions with toll functions [t.sub.n] = ??([n.sup.a][[Delta].sub.n]), [t'.sub.n] = O([log.sup.c] n [multiplied by] [[Epsilon].sub.n]) and ??([log.sup.-1] n), respectively, as stated in Lemma 5.4. Then [F.sub.n] = ??([t.sub.n]), [G.sub.n] = ??([t'.sub.n] log n) and [H.sub.n] = ??(log log n). Moreover, [F.sub.n], = [Theta]([t.sub.n]) if [F.sub.n] [is greater than or equal to] 0 and [t.sub.n] = ??([n.sup.a][[Delta].sub.n]).

The last theorem of this section allows us to compute the constant factor of the leading term of the solution of some recurrences.

THEOREM 5.6. Let [F.sub.n] be defined by a canonical recursive definition, and let [[Gamma].sub.n] be a bounding function of [t.sub.n]. Furthermore, assume that [H.sup.([Gamma])] exists. Then [F.sub.n] = [t.sub.n][[Gamma].sub.n]/[H.sup.([Gamma])] + o([t.sub.n][[Gamma].sub.n]).

PROOF. From the proof of Theorem 5.3 we know that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So, if [H.sup.([Gamma])] exists, it is strictly positive. Define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For n [is greater than or equal to] [N.sub.[Gamma]], use the definition of [G.sub.n] in both directions, like in the proof of Theorem 5.3. This yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [t'.sub.n] denote the toll function above, and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [t'.sub.n] = [t.sub.n] -([H.sup.([Gamma])] + [h.sub.n])/[H.sup.([Gamma])] [multiplied by] [t.sub.n] = [-h.sub.n][t.sub.n]/[H.sup.([Gamma])] = o([t.sub.n]), because [h.sub.n] = o(1). Therefore, it suffices to apply Theorem 5.3 to get [G.sub.n] = o([t.sub.n][[Gamma].sub.n]), which implies [F.sub.n] = [t.sub.n][[Gamma].sub.n]/[H.sup.([Gamma])] + [G.sub.n] = [t.sub.n][[Gamma].sub.n]/[H.sup.([Gamma])] + o([t.sub.n][[Gamma].sub.n]). []

As an example of application of Theorem 5.6, we can easily compute the expected number of comparisons to find a key chosen at random in a trie with n keys, when the digits are independent and equally likely to be 0 or 1. The recurrence is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(It would be a simple matter to write another recurrence with range 0 ... n - 1 for k.) Note that this recurrence is not covered by any of the MTs presented in this work; however, we can solve it anyway. The entropy with respect to ln n is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The distribution of weights gets closer to n/2 as long as n grows. This implies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [H.sup.(ln)] = ln 2, and [T.sub.n] ~ ln n/ln 2 = [log.sub.2] n.

More formally, we can use the fact that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for any 0 [is less than or equal to] [Epsilon] [is less than or equal to] 1 (see Hagerup and Rub [1990, page 306]), and set [Epsilon] = [[Epsilon].sub.n] = [n.sup.- 1/3] to get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

On the other hand, it is easy to prove an upper bound ln 2 for [H.sup.(ln)]. Therefore, [H.sup.(ln)] = ln 2, and finally [T.sub.n] ~ [log.sub.2] n.

6. Proof of the Discrete Master Theorem

In this section, we will derive the Discrete MT. While doing this, we will repeatedly make use of the quantities introduced in Definitions 2.1, 4.1 and 4.2.

LEMMA 6.1. [Phi](x) is a strictly decreasing continuous function such that [lim.sub.x [right arrow] + [infinity]] [Phi](x) = 0 and [lim.sub.x [right arrow] -[infinity] [Phi](x) = +[infinity].

PROOF. By elementary calculus. []

LEMMA 6.2. A discrete recursive definition is canonical if and only if [Phi](0) = 1.

PROOF. For the "only if" proof, we observe that W = [lim.sub.n [right arrow] + [infinity]] [W.sub.n] = [[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] [W.sub.d] = [Phi](0).

For the "if" proof, the definition of discrete recursive definition tells us that |[m.sub.n]| = |[W.sub.n] - [Phi](0)| [is less than or equal to] [[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D]|[r.sub.d,n]| = O([n.sup.-[Rho]]). Furthermore, Z = [lim.sub.n [right arrow] [infinity]] [Z.sub.n] = [[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] [W.sub.d] [multiplied by] [z.sub.d] = [Phi](1), which by Lemma 6.1 is strictly smaller than 1 when W = [Phi](0) = 1.

Theorem 6.3 justifies the cases 2.3 and 3 of the Discrete MT when the recurrence is canonical, that is, when [Alpha] = 0. Note that the case 2.3 reduces to a = 0 and c [is less than] -1, and the condition H [is less than] 0 in the case 3 is equivalent to a [is less than] 0.

THEOREM 6.3. Let [C.sub.n] be defined by a canonical discrete recursive definition, and let [t.sub.n] = ??([log.sup.c] n), where c [is less than] -1. Then [C.sub.n] = ??(1). Moreover, [C.sub.n] = [Theta](1) if [C.sub.n] [is greater than or equal to] 0 for every n [is greater than or equal to] 0 and [t.sub.n] [is greater than] 0 for n large enough.

PROOF. It is enough to realize that [[Sigma].sub.0 [is less than or equal to] k [is less than] N] [w.sub.n, k] = 0 for large n, and use Theorems 4.3 and 4.4. []

For the next step, we need to define the concept of subpolynomial function formally.

Definition 6.4. Let [[Lambda].sub.n],, be a strictly positive nondecreasing function for large n. Moreover, assume that for every [Epsilon] [is greater than] 0 the function [n.sup.[Epsilon]]/[[Lambda].sub.n] is increasing as long as n is large enough. Then we say that [[Lambda].sub.n] is a subpolynomial function.

Lemma 6.5 is used to prove Theorems 6.6 and 7.10.

LEMMA 6.5. Let [t.sub.n] = [n.sup.a][[Xi].sub,n], where a [is greater than] 0 and [[Xi].sub.n] = [[Lambda].sub.n] or [[Xi].sub.n] = 1/[[Lambda].sub.n] for some subpolynomial function [[Lambda].sub.n]. Then 1 is a bounding function of [t.sub.n].

PROOF. We only need to prove that [n.sup.a][Xi]].sub.n] is as stated by Lemma 5.4, which is obvious when [[Xi].sub.n] = [[Lambda].sub.n]. When [[Xi].sub.n] = 1/[[Lambda].sub.n] it is enough to express [t.sub.n] as [n.sup.a/2] [[Delta].sub.n], with [[Delta].sub.n] = [n.sup.a/2]/[[Lambda].sub.n]. []

Theorem 6.6 corresponds to the case 1 of the Discrete MT when [Alpha] = 0 and a [is greater than] 0. The statement of the MT applies to toll functions with subpolynomial factors that are ??([log.sup.c] n) for some c, which is more restrictive than the functions considered by Theorem 6.6.

THEOREM 6.6. Let a function be defined by a canonical discrete recursive definition, and let [t.sub.n] = [n.sup.a][[Xi].sub.n], where a [is greater than] 0 and [[Xi].sub.n] = [[Lambda].sub.n] or [[Xi].sub.n] = 1/[[Lambda].sub.n], for some subpolynomial function [[Lambda].sub.n]. Then [H.sup.(1)] = 1 - [Phi](a).

PROOF. Let us assume [[Xi].sub.n] = [[Lambda].sub.n]. Then, for large n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any 1 [is less than or equal to] d [is less than or equal to] D and any [Epsilon] [is greater than] 0, as long as n is large enough. Moreover, the contribution to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of [r.sub.d,n] and [S.sub.d,n] vanishes for large n. Altogether,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This is true no matter how small [Epsilon] is, and [Phi](x) is a continuous function. We can thus conclude [H.sup.(1)] = 1 - [Phi](a).

A similar argument proves the case [[Xi].sub.n] = 1/[[Lambda.sub.n]. []

Note that the MTs do not deal with toll functions whose growing rate is larger than polynomial, like [2.sup.n]. Nevertheless, several of the results in this work also apply to superpolynomial toll functions, which are formally defined as follows:

Definition 6.7. Let [u.sub.n] be a positive function for large n. For every a [is greater than] 0, assume that [u.sub.n]/[n.sup.a] is increasing as long as n is large enough. Then we say that [u.sub.n] is a superpolynomial function.

Notice that the conditions in the first case of Lemma 5.4 trivially hold for any superpolynomial function. As a consequence, the statement of Corollary 5.5 for toll functions like [t.sub.n] = ??([n.sup.a][[Delta].sub.n]) is true not only for polynomial toll functions but for superpolynomial toll functions as well.

The next theorem deals with discrete recurrences when the toll function is superpolynomial.

THEOREM 6.8. Let a function be defined by a canonical discrete recursive definition, and let [t.sub.n] be a superpolynomial function. Then [H.sup.(1)] = 1.

PROOF. The proof is very similar to that of Theorem 6.6. It is enough to realize that [H.sup.(1)] [is greater than or equal to] 1 - [Phi](a) for every a [is greater than] 0, no matter how large a is. []

We require Lemma 6.9 for the statements of Theorems 6.10 and 7.12.

LEMMA 6.9. Let [t.sub.n] = [ln.sup.c] n [multiplied by] [[Xi].sub.n], where c [is greater than] -1 and [[Xi].sub.n] = [[Mu].sub.n] or [[Xi].sub.n] = 1/[[Mu].sub.n] for some sublogarithmical function [[Mu].sub.n]. Then ln n is a bounding function of [t.sub.n].

PROOF. If [[Xi].sub.n] = [[Mu].sub.n], then [t.sub.n] is clearly as stated by Lemma 5.4. If [[Xi].sub.n] = 1/[[Mu].sub.n], we only need to write [t.sub.n] as [ln.sup.(c - 1)/2] n [multiplied by] [[Delta].sub.n], with [[Delta].sub.n] = [ln.sup.(c+1)/2] n/[[Lambda].sub.n]. []

Theorem 6.10 corresponds to the case 2.1 of the Discrete MT when [Alpha] = a = 0.

THEOREM 6.10. Let a function be defined by a canonical discrete recursive definition, and let [t.sub.n] = [ln.sup.c] n [multiplied by] [[Xi].sub.n], where c [is greater than] - 1 and [[Xi].sub.n] = [[Mu].sub.n] or [[Xi].sub.n] = 1/[[Mu].sub.n] for some sublogarithmical function [[Mu].sub.n]. Then [H.sup.(ln)] = -(c + 1)[[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] [w.sub.d] [multiplied by] ln [z.sub.d].

PROOF. Let us assume [[Xi].sub.n] = 1/[[Mu].sub.n] (the case [[Xi].sub.n] = [[Mu].sub.n] is similar). Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for large n. Besides,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for any 1 [is less than or equal to] d [is less than or equal to] D and any [Epsilon] [is greater than] 0, as long as n is large enough. Furthermore, ln([z.sub.d] + [s.sub.d,n]/n) = ln [z.sub.d] + O([n.sup.-[Sigma]]) for some [Sigma] [is greater than] 0. Thus,

[ln.sup.c+1][S.sub.d,n] = [(ln n + ln [z.sub.d] + ??([n.sup.-[Sigma]])).sup.c+1]

= [ln.sup.c+1]n + (c + 1)[ln.sup.c] n ln [z.sub.d] + ??([log.sup.c-1]n) + ??([n.sup.-[Sigma]] [log.sup.c] n).

Taking into account that ??([log.sup.c-1] n) + ??([n.sup.-[Sigma]] [log.sup.c] n) = ??([log.sup.c-1] n), and that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

we can bound [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where, for the last step, we have used the fact that W = 1. A similar reasoning yields the bound

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From these last two bounds, and since the one above holds for any [Epsilon] [is greater than] 0, the theorem is proved. []

Finally, Theorem 6.11 corresponds to the case 2.2 of the Discrete MT when [Alpha] = a = 0.

THEOREM 6.11. Let a function be defined by a canonical discrete recursive definition, and let [t.sub.n] = [ln.sup.-1] n. Then [H.sup.(ln [multiplied by] ln ln)] = -[[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] [w.sub.d] [multiplied by] ln [z.sub.d].

PROOF. By the definitions of entropy and discrete recursive definition,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as long as n is large enough. Let y = ln n. Recall that |[r.sub.d,n]| = O([n.sup.-[Rho]]) and |[s.sub.d,n]|/n = ??([n.sup.-[Sigma]]). Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The contributions of the terms ??(exp(-[Rho]y)) and ??(exp(-[Sigma]y)) vanish for large y. Thus,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now it suffices to use l'Hopital's rule to get the statement of the theorem. []

To derive both the Discrete and the Continuous MTs, we will use the fundamental property that every discrete or continuous recursive definition is either canonical or can be reduced to a canonical one by means of a definition like [C.sub.n] = [F.sub.n]/[n.sup.[Alpha]], for some appropriate constant [Alpha]. This concept is formalized as follows:

Definition 6.12. Let F be a DAC recursive definition of a function [F.sub.n]. We say that F is a proper DAC recursive definition if and only if there exists some constant [Alpha] such that, if we define [C.sub.n] = [F.sub.n]/[n.sup.[Alpha]], then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a canonical recursive definition.

For instance, any canonical recursive definition is a proper DAC recursive definition with [Alpha] = 0, that is, with [C.sub.n] = [F.sub.n]. Typically, W [is greater than or equal to] 1, and then [Alpha] is positive. For W smaller than 1 (which is not usual in practice) [Alpha] is negative, which is problematic for small indices. This is why we required W to be at least 1 for continuous recursive definitions; note that the term [(k/n).sup.[Alpha]] is unbounded for small k and negative [Alpha]. By contrast, for discrete recursive definitions we allowed W to be smaller than 1; this is a reason to avoid the case [z.sub.d] = 0.

As an example of nonproper DAC recursive definition, we have (7); it is easy to see that it is not canonical nor can be converted into canonical through a change like [C.sub.n] = [F.sub.n]/[n.sup.[Alpha]]. Theorems 6.13 and 7.14 state that this is never the case with discrete and continuous recursive definitions.

THEOREM 6.13. All discrete recursive definitions are proper DAC recursive definitions whose [Alpha] is the unique solution of [Phi]([Alpha]) = 1.

PROOF. From Lemma 6.1, [Phi]([Alpha]) = 1 has always a unique solution. Define [C.sub.n] = [F.sub.n]/[n.sup.[Alpha]]. Then, for large n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [R'.sub.d,n] = ([w.sub.d] + [r.sub.d,n])[([z.sub.d] + [s.sub.d,n]/n).sup.[Alpha]]. Set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [r'.sub.d,n] = [R'.sub.d,n] - [w'.sub.d]. Then we have [[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] |[r'.sub.d,n]| = ??([n.sup.-[Rho]] + [n.sup.-[Sigma]]).

Let [W.sub.n], W, etc. be defined over the new weights. On the one hand, [W.sub.n] = [[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] [R'.sub.d,n] = [[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D]([w'.sub.d] + [r'.sub.d,n]), and W = [[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D]([w'.sub.d] = [Phi]([Alpha]) = 1. Furthermore, |[m.sub.n]| = |[W.sub.n] - W| [is less than or equal to] [[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] |[r'.sub.d,n]| = ??([n.sup.-[Rho]] + [n.sup.-[Sigma]]). On the other hand,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and hence Z = [[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] [w'.sub.d] [multiplied by] [z.sub.d] = [Phi]([Alpha] + 1) [is less than] 1. The theorem follows. []

We now make use of Theorems 5.6 and 6.13 to summarize Theorems 6.3, 6.6, 6.8, 6.10, and 6.11 into Corollary 6.14. This corollary also includes the corresponding results for continuous recurrences (Theorems 7.9, 7.10, 7.11, 7.12, and 7.13), which will be presented and proved in Section 7.

COROLLARY 6.14. Let [F.sub.n] be defined by a discrete (respectively, continuous) recursive definition, and let [Alpha] be the unique solution to [Phi]([Alpha]) = 1 (respectively, [Psi]([Alpha]) = 1).

--If [t.sub.n] = ??([n.sup.[Alpha]] [log.sup.c] n), where c [is less than] - 1, then [F.sub.n] = ??([n.sup.[Alpha]]). Moreover, [F.sub.n] = [Theta]([n.sup.[Alpha]]) if [F.sub.n] [is greater than or equal to] 0 for every n [is greater than or equal to] 0 and [t.sub.n] [is greater than] 0 for large n.

--If [t.sub.n] = [n.sup.[Alpha]][[Xi].sub.n], where a [is greater than] [Alpha] and [[Xi].sub.n] = [[Lambda].sub.n] or [[Xi].sub.n] = 1/[[Lambda].sub.n] for some subpolynomial function [[Lambda].sub.n], then [F.sub.n] ~ [t.sub.n]/(1 - [Phi](a)) (respectively, [F.sub.n] ~ [t.sub.n]/(1 - [Psi](a))).

--If [t.sub.n] is a superpolynomial function, then [F.sub.n] ~ [t.sub.n].

--If [t.sub.n] = [n.sup.[Alpha]] [ln.sup.c] n [multiplied by] [[Xi].sub.n], where c [is greater than] -1 and [[Xi].sub.n] = [[Mu].sub.n] or [[Xi].sub.n] = 1/[[Mu].sub.n] for some sublogarithmical function [[Mu].sub.n], then [F.sub.n] ~ [t.sub.n] ln n/H, where H = -(c + 1)[[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] [w.sub.d] [multiplied by] [([z.sub.d]).sup.[Alpha]] ln [z.sub.d] (respectively, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

--If [t.sub.n] = [n.sup.[Alpha]] [ln.sup.-1] n, then [F.sub.n] ~ [t.sub.n] ln n [multiplied by] ln ln n/H, where H = -[[Sigma].sub.1 [is less than or equal to] d [is less than or equal to] D] [w.sub.d] [multiplied by] [([z.sub.d]).sup.[Alpha]] ln [z.sub.d] (respectively, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]).

7. Proof of the Continuous Master Theorem

We begin with the conjecture included in Definition 3.1.

CONJECTURE 7.1. For every positive function [Omega](z) such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges, there exists some [Mu] [is less than] 0 such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] also converges.

The author of this paper could not prove that, irrespective of [Omega](z), the integral [Psi](x) converges for every x [element of] [[Mu], 0] for some [Mu] [is less than] 0, though no counterexample of this statement was found. However, this property clearly holds for the shape functions we usually deal with. For instance, if [Omega](z) is bounded near 0, then any [Mu] [is greater than] -1 fulfills the condition above. To the best of the author's knowledge, it is an open problem to determine if the statement of Conjecture 7.1 is always true.

The following lemma provides an easy way to find the shape function of many continuous recurrences.

LEMMA 7.2. Let [[Omega].sub.n,k] = A [multiplied by] [f.sub.1] ... [f.sub.m]/([g.sub.1] ... [g.sub.m+1]) be the weights of a given recurrence, where A [is greater than] 0 is an arbitrary constant, m [is greater than or equal to] 0 is any integer constant, [f.sub.i] = ([a.sub.i]n + [b.sub.i]k + [c.sub.i]) for all 1 [is less than or equal to] i [is less than or equal to] m for some constants [a.sub.i], [b.sub.i], and [c.sub.i] such that at least one of [a.sub.i] or [b.sub.i] is not 0, and [g.sub.i] = (n + [d.sub.i]) for all 1 [is less than or equal to] i [is less than or equal to] m + 1, where the [d.sub.i]'s are arbitrary constants. Set [[Sigma].sub.n,k] = A [multiplied by] ([a.sub.1]n + [b.sub.1]k) ... ([a.sub.m]n + [b.sub.m]k)/[n.sup.m+1] and [Omega](z) = n [multiplied by] [[Sigma].sub.n,zn], and suppose that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is at least 1. Then the given recurrence is continuous and [Omega](z) is its shape function.

PROOF. First, we prove that there exists some [Mu] [is less than] 0 such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges. Since [Omega]'(z) exists and is bounded in [0, 1], [Omega](z) is also bounded in [0, 1]. Set h = [max{[Omega](z)}.sub.0 [is less than or equal to] z [is less than or equal to] 1, and choose any -1 [is less than] [Mu] [is less than] 0. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

To prove the conditions in Definition 3.2, let B [is greater than or equal to] 0 be such that |[Omega]'(z)| [is less than or equal to] B for every 0 [is less than or equal to] z [is less than or equal to] 1. It is easy to see that this bound produces

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and its symmetric [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Now, we set [M.sub.n] = n to get [[Epsilon].sub.n,k] [is less than or equal to] B/[2n.sup.2] and [[Sigma].sub.0 [is less than or equal to] k [is less than or equal to] n] [[Epsilon].sub.n,k] = ??([n.sup.-1]). Finally, it is enough to notice that |[[Omega].sub.n,k] - [[Sigma].sub.n,k]| = O([n.sup.-2]) to obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

Hereafter, we will present results for continuous recurrences that are equivalent to those for discrete recurrences in Section 6, together with some technical propositions.

LEMMA 7.3. [Psi](x) is a strictly decreasing continuous function in the interval [[Mu], + [infinity]), such that [lim.sub.x [right arrow] + [infinity]] [Psi](x) = 0.

PROOF. By hypothesis, [Psi](0) [is greater than or equal to] 1. This implies that there are [z.sub.1] and [z.sub.2] such that 0 [is less than] [z.sub.1] [is less than] [z.sub.2] [is less than] 1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For every x [is less than] y such that [Psi](x) and [Psi](y) exist,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, [Psi](x) is a strictly decreasing function.

Proving that [Psi](x) tends to 0 as long as x grows is not more difficult. For every [Epsilon] [is greater than] 0, let 0 [is less than] [z.sub.[Epsilon]] [is less than] 1 be large enough to get [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Assume x [is greater than or equal to] 0. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for x large enough.

It is left to prove that [Psi](x) is a continuous function. Recall that [Mu] [is less than] 0 is the constant such that, according to Conjecture 7.1, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] converges. Choose any a such that a [is greater than] [Mu]. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

The following two technical propositions will be used in several proofs in this section.

PROPOSITION 7.4. Let a function be defined by a continuous recursive definition. For every x [is greater than] 0, define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for all 0 [is less than or equal to] j [is less than] [M.sub.n]. Then for every x [is greater than] 0, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [Sigma] [is greater than] 0.

PROOF. First of all, notice that [[Epsilon].sub.n,j](0) equals [[Epsilon].sub.n,j]. Take any 0 [is less than or equal to] j [is less than] [M.sub.n], and assume that the first term in the definition of [[Epsilon].sub.n,j](x) is larger than the second term. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now, if we set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

then it is easy to see that [(j + 1).sup.x] - [j.sup.x] [is less than or equal to] [[Psi].sub.n]. Moreover, j [is less than] [M.sub.n]. Hence, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If the second term in the definition of [[Epsilon].sub.n.j](x) is larger than the first one, a similar reasoning yields [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Altogether,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Finally, taking into account that [[Psi].sub.n]/[([M.sub.n]).sup.x] = ??([n.sup.-qx]) when 0 [is less than] x [is less than or equal to] 1 and [[Psi].sub.n]/[([M.sub.n]).sup.x] = ??([n.sup.-q]) when x [is greater than] 1, we can bound the expression above by ??([n.sup.-[Sigma]]) for some [Sigma] [is less than] 0 small enough. []

PROPOSITION 7.5. Let a function be defined by a continuous recursive definition. Then, for every x [is greater than] 0, [[Sigma].sub.0 [is less than or equal to] k [is less than] n] [[Omega].sub.n,k][(k/n).sup.x] = [Psi](x) + O([n.sup.-[Sigma]] for some [Sigma] [is greater than] 0.

PROOF. It is enough to observe that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which is not larger than [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. But, according to Proposition 7.4, this sum is ??([n.sup.-[Sigma]]) for some [Sigma] [is greater than] 0. []

LEMMA 7.6. A continuous recursive definition is canonical if and only if [Psi](0) = 1.

PROOF. For the "only if" proof, a reasoning similar to the one in Proposition 7.5 yields |[W.sub.n] - [Psi](0)| = ??([n.sup.-[Rho]). Hence, [Psi](0) has to equal 1 for the recurrence to be canonical.

For the "if" proof, when [Psi](0) = W = 1, we have |[m.sub.n]| = ??([n.sup.-[Rho]]). Moreover, [W.sub.n][Z.sub.n] = [[Sigma].sub.0 [is less than or equal to] k [is less than] n] [[Omega].sub.n,k] k/n = [Psi](1) + ??([n.sup.- [Sigma]]) for some [Sigma] [is greater than] 0 small enough. Now, taking into account that [W.sub.n] = 1 + ??([n.sup.-[Rho]]), we obtain [Z.sub.n] = [Psi](1) + ??([n.sup.-[Sigma]] + [n.sup.-[Rho]]), and conclude that Z = [Psi](1) [is less than] 1. []

We require just two more technical propositions before proving the main results for continuous recurrences.

PROPOSITION 7.7. Let [[Omega].sub.n,k] be the weights of a continuous recursive definition, [f.sub.n] be any function such that [f.sub.n] = [Omega](1) and [f.sub.n] = o(n), x [is greater than or equal to] 0, and [Rho] [is greater than] 0 and 0 [is less than] q [is less than or equal to] 1 be the constants in the definition of continuous recursive definition. Define [h.sub.n] = max{[f.sub.n], [n.sup.1-q]}. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [Mu] [is less than] 0 is such that [Psi]([Mu]) converges.

PROOF. Assume x = 0. Let [g.sub.n] = [Theta]([h.sub.n] [multiplied by] [n.sup.q-1]) be a function with integer values such that [g.sub.n] [multiplied by] n/[M.sub.n] [is greater than or equal to] [f.sub.n] for large n (notice that this implies [g.sub.n] [is greater than or equal to] 1). Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for large n. On the other hand,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Furthermore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which can be bounded by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Altogether, the proposition is proved for the case x = 0.

The proof for x [is greater than] 0 is now trivial, since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

PROPOSITION 7.8. Let [[Omega].sub.n,k] be the weights of a continuous recursive definition, x [is greater than or equal to] 0, and N [is greater than or equal to] 1 be any constant. Then [[Sigma].sub.O [is less than or equal to] K [is less than] N] [[Omega].sub.w,k] (K/n).sup.x] for some u [is greater than] 0.

PROOF. It is enough to use Proposition 7.7 with [f.sub.n] = N. Then [h.sub.n] = [Theta]([n.sup.1-q]) and the sum above is bounded by ??(max{[n.sup.-[Rho]], [n.sup.[Mu]q]}). []

THEOREM 7.9. Let [C.sub.n] be defined by a canonical continuous recursive definition, and let [t.sub.n], = ??([log.sup.c] n), where c [is less than] -1. Then [C.sub.n], = ??(1). Moreover, [C.sub.n], = [Theta](1) if [C.sub.n] [is greater than or equal to] 0 for every n [is greater than or equal to] 0 and [t.sub.n] [is greater than] 0 for n large enough.

PROOF. By Proposition 7.8, we have [[Sigma].sub.0] [is less than or equal to] k [is less than] N] [w.sub.n,k] = ??([n.sup.-u]) for some u [is greater than] 0. Hence, we only need to use Theorems 4.3 and 4.4 to complete this proof. []

THEOREM 7.10. Let a function be defined by a canonical continuous recursive definition, and let [t.sub.n] = [n.sup.a] [[Xi].sub.n], where a [is greater than] 0 and [[Xi].sub.n] = [[Lambda].sub.n] or [[Xi].sub.n] = 1/[[Lambda].sub.n], for some subpolynomial function [[Lambda].sub.n]. Then [H.sup.(1)] = 1 - [Psi](a).

PROOF. Let us assume [[Xi].sub.n] = 1/[[Lambda].sub.n]. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By hypothesis, for every [Epsilon] [is greater than] 0 there exists some [N.sub.[Epsilon]] such that [k.sup.[Epsilon]]/[[Lambda].sub.k] [is less than or equal to] [(k + 1).sup.[Epsilon]]/ [[Lambda].sub.k+1] and [[Lambda].sub.k] [is less than or equal to] [[Lambda].sub.k+1] for all k [is greater than or equal to] [N.sub.[Epsilon]]. Choose any 0 [is less than] [Epsilon] [is less than] a, and let k and n be such that [N.sub.[Epsilon]] [is less than or equal to] k [is less than] n. Then we have [k.sup.[Epsilon]]/[[Lambda].sub.k] [is less than or equal to] [n.sup.[Epsilon]] /[[Lambda].sub.n] and [[Lambda].sub.k] [is less than or equal to] [[Lambda].sub.n]. Therefore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now we can set [N.sub.[Gamma]] = [N.sub.[Epsilon]] to get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

From Propositions 7.5 and 7.8, we deduce 1 - [Psi](a) [is greater than or equal to] [H.sup.(1)] [is greater than or equal to] 1 - [Psi](a - [Epsilon]), which is true no matter how small [Epsilon] is. Since [Psi](x) is a continuous function, we conclude [H.sup.(1)] = 1 - [Psi](a).

A similar argument proves the case [[Xi].sub.n] = [[Lambda].sub.n]. []

THEOREM 7.11. Let a function be defined by a canonical continuous recursive definition, and let tn be a superpotynomial function. Then [H.sup.(1)] = 1.

PROOF. The proof is very similar to that of Theorem 7.10. []

THEOREM 7.12. Let a function be defined by a canonical continuous recursive definition, and let [t.sub.n] = [ln.sup.c] n [multiplied by] [[Xi].sub.n], where c [is greater than] -1 and [[Xi].sub.n] = [[Mu].sub.n], or [[Xi].sub.n], = 1/[[Mu].sub.n], for some sublogarithmical function [[Mu].sub.n]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

PROOF. First of all, we must make sure that [H.sup.(ln)] exists and is strictly positive. It is easy to prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], if exists, is strictly greater than 0. Proving that it does not diverge is not more difficult. Let [Mu] [is less than] 0 be such that [Psi]([Mu]) converges, and let 0 [is less than] u [is less than] 1 be such that -ln z [is less than or equal to] [z.sup.[Mu]] in the interval (0, u]. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now, assume [[Xi].sub.n] = 1, that is, [t.sub.n] = [ln.sup.c] n. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [g.sub.n] = [Theta]([n.sup.d]) be a function with integer values, where d = q/2. So, we have 0 [is less than] d [is less than] q and 0 [is less than] d + 1 - q [is less than] 1. For large n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The term -[m.sub.n] ln n above vanishes because [m.sub.n] = ??([n.sup.-[Rho]). Moreover, the second line above is positive, and can be bounded by ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) ln n. Setting [f.sub.n] = [Theta]([n.sup.1-q/2]) in Proposition 7.7 proves that this sum also vanishes for large n. The rest of the proof is devoted to find the limit of the term that is left.

For every [g.sub.n] [is less than or equal to] j [is less than] [M.sub.n], define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Assume that the first term above is larger than the second one. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Taking into account the facts that -ln([g.sub.n]/[M.sub.n]) = [Theta](log [n.sup.q-d]) = ??(log n) and ln(1 + 1/[g.sub.n]) = [Theta](1/[g.sub.n]) = ??([n.sup.-d]), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If the second term in the definition of [[Delta].sub.n,j] above is larger than the first one, by means of a similar reasoning, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, we can conclude

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which vanishes for large n, because the sum of [[Epsilon].sub.n,j]'s is ??([n.sup.-[Rho]) for some [Rho] [is greater than] 0. Now we are ready to finish the proof, since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is bounded by above by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This ends the proof of the case [[Xi].sub.n] = 1.

The cases [[Xi].sub.n] = [[Mu].sub.n] and [[Xi].sub.n] = 1/[[Mu].sub.n] for sublogarithmical [[Mu].sub.n] = [Omega](1) can be proved by similar arguments (see the proof of Theorem 6.10). []

THEOREM 7.13. Let a function be defined by a canonical continuous recursive definition, and let [t.sub.n] = [ln.sup.-1] n. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

PROOF. This proof follows the same pattern as the one of Theorem 7.12. Therefore, we skip some steps, for the sake of brevity.

Let [v.sub.n] = exp([square root of ln n]), and [g.sub.n] = [Theta]([n.sup.q]/[v.sub.n]) be a function with integer values. By the definitions of entropy and continuous recursive definition,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as long as n is large enough. The term -[m.sub.n] ln n [multiplied by] ln ln n clearly vanishes for large n. Moreover, the second line above is positive, and bounded by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ln n ln ln n. By Proposition 7.7, this term is also o(1), since [f.sub.n] = [h.sub.n] =n/[v.sub.n] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Below, we prove that the limit of the remaining term above is as stated by the theorem.

For every [g.sub.n] [is less than or equal to] j [is less than] [M.sub.n], define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Assume that the first term above is larger than the second one (the opposite produces a similar bound). Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now it is not difficult to get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The contribution to the entropy of the second line is asymptotically irrelevant, because ln(1 + 1/[g.sub.n]) = [Theta](1/[g.sub.n]) = o(1). For the next step, we show that the factor ln n [multiplied by] ln (1 - ln(1/[z.sub.n,j])/ln n) equals ln [z.sub.n,j] + o(1), which is easy if we take into account the fact that 1/[z.sub.n,j] = ??([M.sub.n]/[g.sub.n]) = ??([v.sub.n]). Hence, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], ln(1/[z.sub.n,j]) = ??(ln [v.sub.n]) = ?? ([cube root of ln n]), which implies ln(1/[z.sub.n,j])/ln n = ??([ln.sup.-2/3] n) = o(1). Finally, we observe that ln(1 - x) = -x + ??([x.sup.2]) when x = o(1) to conclude

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now it is enough to follow the last steps in the proof of Theorem 7.12 to finish this proof. []

THEOREM 7.14. All continuous recursive definitions are proper DAC recursive definitions whose [Alpha] is the unique solution of [Psi]([Alpha]) = 1.

PROOF. From Lemma 7.3 and [Psi](0) [is greater than or equal to] 1, the equation above has a unique solution. Define [C.sub.n] = [F.sub.n]/[n.sup.[Alpha]]. Then, for every n [is greater than or equal to] N,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From Propositions 7.4 and 7.8, it is a simple matter to prove that [Omega](z)[z.sup.[Alpha]] is the shape function of C (just set x = [Alpha]). Moreover, since [Psi]([Alpha]) = 1, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This proves that the recurrence for [C.sub.n] is a canonical continuous recursive definition.

As a final remark, notice that the term (1/[n.sup.[Alpha]]) [[Sigma].sub.0 [is less than or equal to] k [is less than] N] [[Omega].sub.n,k] [F.sub.k] in [t'.sub.n] is ??([n.sup.-[Alpha]-[Mu]) for some u [is greater than] 0 (use Proposition 7.8), and hence we are allowed to forget about the contribution of this term to the main term of [C.sub.n]. []

8. Computing the Variance

We have devoted previous sections to analyze the (expected) cost of algorithms. However, if the executions are random (in the different possible inputs of the same size; or in the different possible executions with the same input, if the algorithm is randomized), then the variance of the cost is also a valuable measure. In this section, we will analyze the variance of two types of algorithms.

8.1. ONE-BRANCH ALGORITHMS. The first class includes the algorithms that perform one recursive call with probability 1 - [S.sub.n], and otherwise stop the recursion chain with probability [S.sub.n], where [S.sub.n] tends to zero as long as n grows. FIND is a prototypical example of this class. It divides the original array into two parts, and afterwards recursively continues in the subarray to the left or in the subarray to the right of the current pivot, or either stops with probability 1/n. In this setting, [[Omega].sub.n,k] is the probability that the algorithm performs the recursive call over a subproblem with size k when the original problem has size n.

Let [T.sub.n] be the random variable that describes the nonrecursive cost, including both the cost to split the problem and the cost to combine the recursive solutions. We assume that these two costs do not depend on the particular input nor the recursive solutions, but eventually depend on which was the "pivot" (whatever it means depending on the algorithm). We also assume that the following symmetry holds:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Under this hypothesis, the size of the recursive call implicitly gives us which was the pivot (or its symmetric).

Let the total cost of the algorithm be described by the random variable [F.sub.n], and let [P.sub.n,j] = Pr{[F.sub.n] = j). Of course, we have [[Sigma].sub.j [is greater than or equal to] 0] [P.sub.n,j] = 1. The [P.sub.n,j]'s satisfy the following recurrence:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The reason for the "[perspective to]" above is that we dismiss the contribution to the cost of the executions that stop the chain of recursive calls, since, by hypothesis, [S.sub.n] tends to zero, and in most practical situations this cost is asymptotically irrelevant.

Let

(14) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

(15) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Define [F.sub.n] = E[[F.sub.n]] = [[Sigma].sub.j [is greater than or equal to] 0] [P.sub.n,j] [multiplied by] j and [G.sub.n] = E[[([F.sub.n]).sup.2]] = [[Sigma].sub.j [is greater than or equal to] 0] [P.sub.n,j] [multiplied by] [j.sup.2]. On the one hand, by means of simple rewriting we obtain

(16) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as expected. Recall that, despite the approximation above, the main term of the solution of the recurrence is indeed the main term of [F.sub.n]. On the other hand, from the equality [j.sub.2] = [(j - i).sup.2] + 2(j - i)i + [i.sup.2], it is straightforward to get

(17) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

To solve this recurrence we need to estimate the sums [[Sigma].sub.k] [[Omega].sub.n,k]Q(n, k) and [[Sigma].sub.k] [[Omega].sub.n,k]E(n, k) [F.sub.k].

Assume that the set of [[Omega].sub.n,k]'s corresponds to a canonical continuous recursive definition, and that [T.sub.n] is not random, that is, [T.sub.n] = [t.sub.n]. Then Q(n, k) = [([t.sub.n]).sup.2], and from E(n, k) = [t.sub.n] and (16) we have [[Sigma].sub.0 [is less than or equal to] k [is less than] n] [[Omega].sub.(n, k)] 2E (n, k) [F.sub.k] [nearly equal to] [2t.sub.n][F.sub.n] - 2[([t.sub.n]).sup.2]. Thus, (17) reduces to

(18) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Notice that this recurrence is a continuous recursive definition with the same shape function as (16).

Suppose first [t.sub.n] ~ [n.sup.a][[Xi].sub.n], where a [is greater than] 0 and [[Xi].sub.n] includes subpolynomial terms. According to the Continuous MT, [F.sub.n] ~ [t.sub.n]/(1 - [Psi](a)). Therefore, the toll function in (18) is ~ [2n.sup.2a][([[Xi].sub.n]).sup.2]/(1 - [Psi](a)) - [n.sup.2a][([[Xi].sub.n]).sup.2] = [n.sup.2a][([[Xi].sub.n]).sup.2](1 + [Psi](a))/(1 - [Psi](a)), and

[G.sub.n] ~ 1 + [Psi](a)/(1 - [Psi](2a))(1 - [Psi](a)) [multiplied by] [([t.sub.n]).sup.2].

Hence, the variance of [F.sub.n], V[[F.sub.n]] = E[[([F.sub.n]).sup.2]] - E[[[F.sub.n]].sup.2], can be computed as

V[[F.sub.n]] ~ [Psi](2a) - [Psi][(a).sup.2]/ (1 - [Psi](2a))[(1 - [Psi](a)).sup.2] [multiplied by] [([t.sub.n]).sup.2].

Suppose now [t.sub.n] ~ [ln.sup.c] n [multiplied by] [[Xi].sub.n], where c [is greater than] -1 and [[Xi].sub.n] includes sublogarithmical terms. Then [F.sub.n] ~ [t.sub.n] ln n/(c + 1)I, where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Replacing this result in (18) yields [G.sub.n] ~ [([t.sub.n]).sup.2] [ln.sup.2] n/[(c + 1).sup.2][I.sup.2], and we can only conclude V[[F.sub.n]] = o[([F.sub.n]).sup.2], but no more precise statement can be made in general.

8.2. TWO-BRANCH ALGORITHMS. These algorithms perform two recursive calls to subproblems with size k and n - 1 - k, respectively, with probability 1 - [S.sub.n]. Otherwise, the algorithm makes no recursive call. Again, [S.sub.n] tends to zero as long as n grows. Quicksort is a prototypical example of this class. It divides the array into two parts, and afterwards it recursively sorts the left and the right subarrays.

Let [[Psi].sub.n,k] be the probability that the original problem of size n is broken into two subproblems of sizes k and n - 1 - k, respectively. Like for one-branch algorithms, assume that the algorithm's cost to break and recombine does not depend on the particular input nor the recursive solutions, but does depend on k, the "pivot." Again, let [P.sub.n,j] = Pr{[F.sub.n] = j}. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let E(n, k) be defined as in (14), and let [F.sub.n] = E[[F.sub.n]]. It is easy to see that [F.sub.n] follows the recurrence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let Q(n, k) be defined as in (15), and let [G.sub.n] = E[[([F.sub.n]).sup.2]]. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using [j.sup.2] = [(j - i - y).sup.2] + 2(j - i - y)i + 2(j - i - y)y + 2iy + [i.sup.2] + [y.sup.2] yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We can solve the recurrences for [F.sub.n] and [G.sub.n] under some particular hypotheses. Assume that E(n, k) = [t.sub.n], Q(n, k) = [([t.sub.n]).sup.2], and that there exists some function [Psi](z) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [Psi](z), [M.sub.n], [I.sub.n,j], [z.sub.n,j] and [Rho] are like in Definition 3.2. Then [F.sub.n] follows the continuous recurrence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [[Omega].sub.n,k] = [[Psi].sub.n,k] + [[Psi].sub.n,n-1-k], and thus [Omega](z) = [Psi](z) + [Psi](1 - z). Moreover, [Alpha] = 1, because

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Also, under the assumptions above, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Suppose first [t.sub.n] ~ [n.sup.a][[Xi].sub.n], where a [is greater than] 1 and [[Xi].sub.n] includes subpolynomial terms. Then [F.sub.n] ~ [t.sub.n]/(1 - [Psi](a)), and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the integral above results from a reasoning similar to those used to derive the Continuous MT. We can conclude

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Suppose now [t.sub.n] ~ n [ln.sup.c] n [multiplied by] [[Xi].sub.n], where c [is greater than] -1 and [[Xi].sub.n] includes sublogarithmical terms. Then [F.sub.n] ~ [t.sub.n] ln n/H, where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Like for one-branch algorithms, we can only conclude V[[F.sub.n]] = o[([F.sub.n]).sup.2], since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For this last step, it is enough to notice that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

9. Open Problems

The results of this work could be extended in other directions. For instance, consider the system of equations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the weights above fulfill the discrete and/or the continuous pattern. The problem is: Can we systematically solve such a system, for a wide set of toll functions and weight distributions?

On the other hand, it would be interesting to dispose of theorems to systematically solve recurrences on more than one variable, like

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the weights above follow a discrete or continuous pattern.

Finally, and mostly of theoretical interest, we could deal with toll functions [t.sub.n] = [n.sup.[Alpha]] [[Delta].sub.n] for some [[Delta].sub.n], subpolynomial and superlogarithmical (like [[Delta].sub.n] = exp([square root of ln n])), or [[Delta].sub.n] = [Omega]([log.sup.-1] n) and [[Delta].sub.n] = o([log.sup.-1+[Epsilon]] n) for every [Epsilon] [is greater than] 0, or [[Delta].sub.n], = o([log.sup.-1] n) and [[Delta].sub.n] = [Omega]([log.sup.-1-[Epsilon]] n) for every [Epsilon] [is greater than] 0. The main interest of the later case would be finding the maximum growing order for [[Delta].sub.n], such that [F.sub.n], = ??([n.sup.[Alpha]]).

ACKNOWLEDGMENTS. I thank my advisor Conrado Martinez for his support while working on this problem, and several referees for their helpful comments.

(1) Through all this work, [log.sup.c] n means [(log n).sup.c].

(2) To the best of the author's knowledge, Kao [1997] was the first to develop a basic MT for this kind of recurrences in 1986 (personal communications). Some additional results about these recurrences may be found in Verma [1997].

(3) The author's conjecture is that this technical property is always true if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] exists and is at least 1. Section 7 provides more details.

(4) Thanks are due to Fatos Xhafa for suggesting this example.

REFERENCES

AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass.

BENTLEY, J. L., HAKEN, D., AND SAXE, J. B. 1980. A general method for solving divide-and-conquer recurrences. SIGACT News 12, 3, 36-44.

CORMEN, T. H., LEISERSON, C. E., AND RIVEST, R. L. 1990. Introduction to Algorithms. The MIT Press, Cambridge, Mass.

FLAJOLET, P., AND COLIN, M. 1994. Mellin transforms and asymptotics. Acta Inf. 31, 673-696.

FLAJOLET, P., GONNET, G., PUECH, C., AND ROBSON, J. M. 1993. Analytic variations on quadtrees. Algorithmica 10, 473-500.

HAGERUP, T., AND RUB, C. 1990. A guided tour of chernoff bounds. Inf. Proc. Lett. 33, 305-308.

HOARE, C. A. R. 1961. FIND (Algorithm 65). Commun. ACM 4, 321-322.

HOARE, C. A. R. 1962. Quicksort. Computer J. 5, 10-15.

KAO, M. 1997. Multiple-size divide-and-conquer recurrences. SIGACT News 28, 2 (June), 67-69.

KARP, R. M. 1994. Probabilistic recurrence relations. J. ACM 41, 6 (Nov.), 1136-1150.

KUO, D., AND CHANG, G. J. 1994. The profile minimization problem in trees. SIAM J. Comput. 23, 1 (Feb.), 71-81.

MARTINEZ, C., AND ROURA, S. 1998. Optimal sample sizes for quicksort and quickselect. Tech. Rep. LSI-98-1-R. Departament de Llenguatges i Sistemes Informatics, Universitat Politecnica de Catalunya, Catalonia, Spain.

ROURA, S. 1997a. Divide-and-conquer algorithms and data structures. Ph.D. dissertation. Departament de Llenguatges i Sistemes Informatics, Universitat Politecnica de Catalunya, Catalonia, Spain.

ROURA, S. 1997b. An improved master theorem for divide-and-conquer recurrences. In Proceedings of the 24th International Colloquium (ICALP '97). Pierpaolo Degano, Roberto Gorrieri, and Alberto Marchetti-Spaccamela, Eds. Lecture Notes in Computer Science, vol. 1256. Springer-Verlag, New York, pp. 449-459.

SEDGEWICK, R., AND FLAJOLET, P. 1996. An Introduction to the Analysis of Algorithms. Addison-Wesley, Reading, Mass.

VERMA, R. M. 1994. A general method and a master theorem for divide-and-conquer recurrences with applications. J. Algorithms 16, 67-79.

VERMA, R. M. 1997. General techniques for analyzing recursive algorithms with applications. SIAM J. Comput. 26, 568-581.

WANG, X., AND FU, Q. 1996. A frame for divide-and-conquer recurrences. Inf. Proc. Lett. 59, 45-51.

RECEIVED JULY 1998; REVISED JULY 2000; ACCEPTED JULY 2000

Appendixes

A. Examples of the Use of the Discrete Master Theorem

We start solving (1). First, we identify the main term of toll function, and the sets of values [{[w.sub.d]}.sub.1 [is less than or equal to] d [is less than or equal to] D] and [{[z.sub.d]}.sub.1 [is less than or equal to] d [is less than or equal to] D]. This yields [t.sub.n] ~ [n.sup.1] [ln.sup.0] n, [w.sub.1] = [w.sub.2] = 1 and [z.sub.1] = [z.sub.2] = 1/2. Note that the bounds for [r.sub.d,n], and [s.sub.d,n] trivially hold here, because Definition 2.1 always covers floors and ceilings. We now define [Phi](x) = 2[(1/2).sup.x], and evaluate H = 1 - [Phi](1) = 0. Since H = 0, we compute H' = -(0 + 1)(2[(1/2).sup.1] ln(1/2)) = ln 2. Therefore, [M.sub.n] ~ n ln n/ln 2 = n [log.sub.2] n.

Let us analyze (2). The main term in its toll function is [n.sup.0] [ln.sup.0] n. Moreover, [w.sub.1] = [w.sub.2] = 1/2 and [z.sub.1] = [z.sub.2] = 1/2. So, we define [Phi](x) = [(1/2).sup.x]. Since H = 1 - [Phi](0) = 0, we compute H' = -(0 + 1)([(1/2).sup.0] ln(1/2)) = ln 2, and conclude [B.sub.n] ~ ln n/ln 2 = [log.sub.2] n.

We now consider (3). Suppose [t.sub.n] = [6n.sup.2]/[ln.sup.5] n. The weights are [w.sub.1] = 2, [w.sub.2] = 4 and [w.sub.3] = 1/2; the fractions are [z.sub.1] = 1/3, [z.sub.2] = 1/2 and [z.sub.3] = 4/5. It is a simple matter to check that this recurrence follows Definition 2.1. So, we define [Phi](x) = 2[(1/3).sup.x] + 4[(1/2).sup.x] + 1/2 [multiplied by] [(4/5).sup.x], and H = 1- [Phi](2)= -122/225. Since H [is less than] 0, we have [F.sub.n] = [Phi]([n.sup.[Alpha]]), where [Alpha] is the unique solution of the equation [Phi]([Alpha]) = 1, which numerically is [Alpha] [nearly equal to] 2.68723.

Solving

f(n) = [Phi](n) + 2f(n/2) + 2f(n/3) + 2f(n/6)

is very similar. It yields f(n) = [Phi]([n.sup.[Alpha]]), where [Alpha] [nearly equal to] 1.72121 is the unique solution of 2[(1/2).sup.[Alpha]] + 2[(1/3).sup.[Alpha]] + 2[(1/6).sup.[Alpha]] = 1. This is an upper bound to the system of equations presented in Kuo and Chang [1994, pp. 79-80], where a very good approximation, [Alpha] [nearly equal to] 1.722, is given.(4)

Finally, set [t.sub.n] = [n.sup.2] for (11). Solving it is very easy: [w.sub.1] = 1 and [z.sub.1] = 1/4; [Phi](x) = [(1/4).sup.x] and H = 1 - [Phi](2) = 15/16; since H [is greater than] 0, we deduce [F.sub.n] ~ [n.sup.2]/(15/16) = [16n.sup.2]/15.

In this example, we can get more information by means of a simple trick. Let [G.sub.n] = [F.sub.n] - [16n.sup.2]/15. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We can now find bounds for [G.sub.n]. Taking into account that n/4 - 3/4 [is less than or equal to] - ??n/4?? [is less than or equal to] n/4, we have [n.sup.2]/16 - 3n/8 + 9/16 [is less than or equal to] [??n/4??.sup.2] [is less than or equal to] [n.sup.2]/16, and hence

-2n/5 + 9/15 + [G.sub.??n/4??] [is less than or equal to] [G.sub.n] [is less than or equal to] [G.sub.??n/4??].

We can use the Discrete MT again to solve [G'.sub.n] = -2n/5 + 9/15 + [G'.sub.??n/4??]. This is even simpler, since the distribution of weights remains unchanged, and so does [Phi](x). The main term in the toll function is negative (-2n/5); recall that this is not a problem. Computing H yields H = 1 - [Phi](1) = 3/4, and therefore [G'.sub.n] ~ -2/5 [multiplied by] n/(3/4) = -8n/15. We now solve [G".sub.n] = G".sub.??n/4??], and get [G".sub.n] = ??([n.sup.[Alpha]]) = ??(1); not [Theta](1), since every term could be zero. Finally, we conclude [F.sub.n] = [16n.sup.2]/15 + [G.sub.n], where -8n/15 + o(n) [is less than or equal to] [G.sub.n] [is less than or equal to] O(1), thus achieving tighter bounds for [F.sub.n]. We will see that for stochastic recurrences this technique provides more accurate results.

B. Examples of the Use of the Continuous Master Theorem

We first analyze (4). It is trivial to show that [Omega](z) = 2. Therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. if x [is greater than] -1 (and [Psi](x) = +[infinity otherwise). Since H = 1 - [Psi](1) = 0, we define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and finally [Q.sub.n] ~ n ln n/(1/2) = (2 ln 2)n [log.sub.2] n [nearly equal to] 1.38n [log.sub.2]n.

To solve (5) we start identifying the shape function for the weights, using Lemma 7.2. First, we replace the term n + 1 in the denominator of [[Omega].sub.n,k] by n. This yields [[Sigma].sub.n,k] = 4(n - k)/[n.sup.2]. Second, we compute [Omega](z) = n [multiplied by] [[Sigma].sub.n,zn] = n [multiplied by] 4(n - zn)/[n.sup.2] = 4(1 - z). Third and last, we check that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] indeed. Now we define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if x [is greater than] -1 (and [Psi](x) = + [infinity] otherwise). Since H = 1 - [Psi](0) = -1 [is less than] 0, we conclude [F.sub.n] = [Theta]([n.sup.[Alpha]]), where [Alpha] is the unique solution of [Psi]([Alpha]) = 1. This yields [Alpha] = ([square root of 17-3])/2 [nearly equal to] 0.56155 (the only solution to [[Alpha].sup.2] + 3[Alpha] - 2 = 0 that is larger than - 1).

We now solve (9), for which we already know that [Omega](z) = 2z. In this case [Psi](x) = 2/(x + 2) if x [is greater than] -2 (and [Psi](x) = + [infinity] otherwise). Since H = 1 - [Psi](1) = 1/3 [is greater than] 0, it follows that [S.sub.n] ~ n/(1/3) = 3n.

In this example, we can get more information, using the technique that was presented in Appendix A. Define [G.sub.n] = [S.sub.n] - 3n. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But [[Sigma].sub.0 [is less than or equal to] k [is less than] n] [k.sup.2] = [n.sup.3]/3 - [n.sup.2]/2 + n/6. Thus,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Notice that, in contrast to what happens with discrete recurrences, the recurrence for [G.sub.n] above does not contain noise terms. Now we use the Continuous MT again. The first step is already done, since the distribution of weights remains the same, and [Psi](x) too. Since H = 1 - [Psi](0) = 0, we compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and get [G.sub.n] ~ -2 ln n/(1/2) = -4 ln n.

We can go one step further, defining [I.sub.n] = [G.sub.n] + [4H.sub.n], which is slightly simpler than defining [I.sub.n] = [G.sub.n] + 4 ln n. Notice that we are extracting the main terms of [S.sub.n] one by one. This step yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where we have used the fact that [[Sigma].sub.0 [is less than or equal to] k [is less than] n] k[H.sub.k] = [n.sup.2][H.sub.n]/2 - [n.sup.2]/4 - n[H.sub.n]/2 + n/4. Now we get H = 1 - [Psi](-1) = -1 [is less than] 0, and hence [I.sub.n] = ??([n.sup.[Alpha]]) = ??(1); we cannot deduce [I.sub.n] = [Theta](1), since the toll function in the definition of [I.sub.n] includes positive and negative terms together. At this point we cannot go any further, because we have reached the core of the recurrence. As a conclusion, we have [S.sub.n] = 3n - 4 ln n+ ??(1).

As a final remark, hybrid recurrences like

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

can be analyzed by combining both MTs. So, to solve this recurrence is enough to find out that [w.sub.1] = 1, [z.sub.1] = 1/2 and [Omega](z) = 1; compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; and conclude [F.sub.n] ~ [n.sup.2]/(5/12) = [12n.sup.2]/5.

SALVADOR ROURA Universitat Politecnica de Catalunya, Barcelona, Catalonia, Spain

This research was supported by the ESPRIT BRA Project ALCOM II, contract #7141, by the ESPRIT LTR Project ALCOM-IT, contract #20244 and by a grant from CIRIT (Comissio Interdepartamental de Recerca i Innovacio Tecnologica). A previous version of this work was partially written while the author was visiting Princeton University.

Author's address: Departament de Llenguatges i Sistemes Informatics, Universitat Politecnica de Catalunya, E-08028 Barcelona, Catalonia, Spain. E-mail: roura@lsi.upc.es.

Printer friendly Cite/link Email Feedback | |

Author: | ROURA, SALVADOR |
---|---|

Publication: | Journal of the Association for Computing Machinery |

Geographic Code: | 1USA |

Date: | Mar 1, 2001 |

Words: | 19586 |

Previous Article: | Short Proofs Are Narrow--Resolution Made Simple. |

Next Article: | Convex Quadratic and Semidefinite Programming Relaxations in Scheduling. |

Topics: |