Identities and periodic oscillations of divide-and-conquer recurrences splitting at half Hsien-Kuei Hwang

2025-05-08 0 0 2.93MB 68 页 10玖币

侵权投诉

Identities and periodic oscillations of

divide-and-conquer recurrences splitting at half*

Hsien-Kuei Hwang

Institute of Statistical Science,

Academia Sinica

Taipei 115

Taiwan

Svante Janson

Department of Mathematics

Uppsala University

Uppsala

Sweden

Tsung-Hsi Tsai

Institute of Statistical Science

Academia Sinica

Taipei 115

Taiwan

Friday 21st October, 2022

Abstract

We study divide-and-conquer recurrences of the form

f(n) = αfn

2+βfn

2+g(n) (n>2),

with g(n)and f(1) given, where α, β >0with α+β > 0; such recurrences appear

often in analysis of computer algorithms, numeration systems, combinatorial sequences,

and related areas. We show that the solution satisﬁes always the simple identity

f(n) = nlog2(α+β)P(log2n)−Q(n)

under an optimum (iff) condition on g(n). This form is not only an identity but also an

asymptotic expansion because Q(n)is of a smaller order. Explicit forms for the continuity

of the periodic function Pare provided, together with a few other smoothness properties.

We show how our results can be easily applied to many dozens of concrete examples col-

lected from the literature, and how they can be extended in various directions. Our method

of proof is surprisingly simple and elementary, but leads to the strongest types of results

for all examples to which our theory applies.

*The work of the ﬁrst author was partially supported by National Science and Technology Council under the

Grant MOST-108-2118-M-001-005-MY3, and part of it was carried out while he was visiting Department of

Mathematics, Uppsala University; he thanks the Department for hospitality and support. Part of the work of the

second author was carried out during visits to the Isaac Newton Institute for Mathematical Sciences (EPSCR Grant

Number EP/K032208/1) and was partially supported by a grant from the Simons Foundation, and a grant from the

Knut and Alice Wallenberg Foundation; he thanks these for hospitality and support.

arXiv:2210.10968v1 [cs.DS] 20 Oct 2022

Contents

1 Introduction 2

2 The recurrence Λα,β[f] = g8

3 Smoothness properties of the periodic function P17

4 Applications, I. α6=β23

4.1 Periodicequivalence ............................... 24

4.2 Λα,β[f]=0 .................................... 25

4.3 (α, β) = (1,2) and (α, β) = (2,1) ........................ 28

4.4 Sequences satisfying Λα,β[f] = gwith α+β>4................ 31

5 Applications II. α=β34

5.1 (α, β) = (1,1) ................................... 35

5.2 (α, β) = (2,2) ................................... 36

5.3 (α, β) = (4,4) ................................... 42

5.4 (α, β) = (10,10) ................................. 43

5.5 Partial sums of Λα,0[f] = g............................ 44

6 Extension to nonpositive αor β46

6.1 Recurrences with α= 0 or β= 0 ......................... 47

6.2 Recurrences with both αand βnegative ..................... 47

6.3 Recurrences with either αor βnegative ..................... 51

7 Extension from binary to q-ary 52

7.1 Binomial coefﬁcients not divisible by a prime q................. 53

7.2 Generating polynomial of Gray codes . . . . . . . . . . . . . . . . . . . . . . 54

Appendices 56

A Mellin transforms 56

B A series representation for ˆ

P(k)60

C Recurrences with minimisation or maximisation 61

D Nowhere differentiability of PA006581(t)64

1 Introduction

This paper is a sequel to [27], where we studied the case (α, β) = (1,1) of the following

recurrence

f(n) = αfn

2+βfn

2+g(n) (n>2),(1.1)

with f(1) and {g(n)}n>2given; we focus here on the general case of two given constants

α, β > 0. (The case when α60or β60is brieﬂy discussed in Section 6.) As in [27], our

aim in this paper will be

• to establish optimum iff-conditions for the identity

f(n) = n%P(log2n)−Q(n) (n>1),(1.2)

which is also an asymptotic expansion, where

%:= log2(α+β),(1.3)

Pis a bounded, continuous,periodic function and Q(n)is of a smaller order o(n%); and

• to explore the usefulness of such a result by examining other associated properties and

applying to many concrete examples.

In addition, we also examine further smoothness properties of the periodic function P, and

introduce and explore a new notion to describe the equivalence of different recurrences.

An elementary interpolation approach. The crucial step of our approach is to identify a

(generally nonlinear) interpolation function ϕ(x)such that the sequence f(n)as deﬁned by

(1.1) for positive integers ncan be extended to a continuous function f(x)deﬁned for all real

x>1in the way that f(x)equals the original sequence f(n)when x=n, a positive integer,

and there is a version of the recurrence (1.1) valid for all x; see Section 2for details.

Such an interpolation-based analysis for (1.1) will then be extended (in Section 7) to the

more general q-ary recurrence (q>2) of the form

f(n) = X

06j<q

αjfn+j

q+g(n) (n>q),(1.4)

for some given constants α0, . . . , αq−1, and a result of the form (1.2) will also be derived under

some conditions. Typical situations where (1.4) arises is the application of divide-and-conquer

into qparts whose sizes are as evenly as possible. The special case when αj= 1 for 06j < q

was already discussed in [27]. Another special case is αj= 0 for 16j6q−2, which yields

(with α=α0and β=αq−1) the recursion f(n) = αf(bn

qc) + βf(dn

qe) + g(n)considered in

[11, Theorem 4.1] and [33] although they allow also non-integer q > 1.

Recurrences with or without ﬂoors and ceilings. While the divide-and-conquer paradigm

with evenly divided parts is widely used in computer algorithms, our formulation of the divide-

and-conquer recurrence (1.4), as well as the very precise identity (1.2), is surprisingly rare in

the computer algorithm literature; instead one ﬁnds predominantly a recurrence of the form

f(n)=(α+β)fn

2+g(n),(1.5)

or more generally

f(n) = X

06j<d

αjfn

qj+g(n),(1.6)

where α, αj>0,d= 1,2, . . . and qj>1. According to the ﬁrst edition of Cormen et al.’s

widely used textbook on Algorithms [10, p. 54]: “When we state and solve recurrences, we

often omit ﬂoors, ceilings, and boundary conditions. We forge ahead without these details and

later determine whether or not they matter. . . . we shall address some of these details to show

the ﬁne points of recurrence solution methods.”

Such a simplifying approach also appears in most publications on Algorithms. One of

our aims in this paper is to show that retaining ﬂoors and ceilings is not much more com-

plicated than omitting them, and with various advantages that are mostly unnoticed in the

literature. This suggests that one main reason of omitting ﬂoors and ceilings in handling a

divide-and-conquer recurrence lies more in methodological deﬁciencies than simply technical

conventions; the approach proposed in this paper will then complete to some extent the required

methodological developments.

More precisely, when α, β, g(n)>0, typical approaches adopted in the computer algo-

rithms community to solving the recurrence (1.1) include

• dropping ﬂoor and ceiling in (1.1) by assuming nto be a power of 2, resulting in the

closed-form expression

f(2m) = X

16j6m

(α+β)m−jg(2j)+(α+β)mf(1),(1.7)

and

• lower- and upper-bounding fby keeping only ﬂoor and only ceiling function in (1.1),

leading to

f−(n) := (α+β)f−bn

2c+g(n),(1.8)

and

f+(n) := (α+β)f+dn

2e+g(n),(1.9)

respectively.

While simple and effective in estimating the growth order of f(n)for large n, both approaches

suffer from subtle oversights and intrinsic limitations, with different shortcomings.

Monotonicity. First, in either of the approaches (1.7) and (1.8)–(1.9), the next crucial prop-

erty used in estimating the asymptotic growth of f(n)is monotonicity, which in the ﬁrst ap-

proach is of the form f(2m)6f(2m+`)6f(2m+1)for 06`62m, and f−(n)6

f(n)6f+(n)in the second approach. However, these inequalities may not hold in gen-

eral due to the periodic nature of the recurrences (1.1), (1.8) and (1.9). For example, take

α=β= 1 and g(n) = 1 + 1nodd with f(1) = f+(1) = 0. Then 8 = f(7) > f(8) = 7,

and f(15) = 17 > f+(15) = 16. Thus the use of the monotonicity is more subtle than it is

generally taken to be.

On the other hand, when g(n) = 1nodd with f(1) = 0 (which yields A296062 in the

On-Line Encyclopedia of Integer Sequences database [34] with many combinatorial interpreta-

tions), then f(n)oscillates between 0and Θ(n). Thus not only monotonicity fails but also the

growth order oscillates violently, although our result yields that f(n) = nP (log2n)for some

continuous periodic function; see (5.7).

Discontinuity. Apart from monotonicity, there is yet another deeper reason why the original

sequence (1.1) is preferred to its simpliﬁed one-sided versions (1.8) and (1.9): the periodic

function Pin (1.2) is always continuous, while the corresponding one for the solution of either

(1.8) or (1.9) is almost always discontinuous; more precisely, in typical cases the function P(t)

is discontinuous at every tsuch that 2tis a dyadic rational, i.e., has a ﬁnite binary representation

(see Section 6.1 and, for details in the case α+β= 2, [27, Section 8]). But why does continuity

matters here? The reason is because the periodic function Pwhen evaluated at log2n(see

(1.2)), involves indeed functions evaluated at the dyadic rational n/2blog2nc(see (2.22) and

(2.30)), so that discontinuity causes the sequence (or the original cost function) to have more

violent jumps even for neighbouring input sizes. Thus simplifying the recurrence (1.1) to either

(1.8) or (1.9) has the advantage of being easily solvable by iteration, but suffers from structural

discontinuities, or more rough oscillations.

Master theorems. Another commonly used approach to solve (1.5) is to apply the so-called

“master theorems” (see [2,11]), which are generally effective and user-friendly, but does not

provide more precise asymptotic approximations. For example, in the case of (1.1), if g(n) =

O(n%−ε),ε > 0, then the master theorem [11, § 4.5] or [33] gives f(n) = Θ(n%), where %is

deﬁned in (1.3), while under the same growth order of g, our approach (see Corollary 2.14)

again guarantees (1.2) with explicitly computable functions Pand Q. There do exist ﬁner

master theorems that give more precise asymptotics under stronger assumptions on g(n)(such

as monotonicity; see [13]), but none of them is as precise as our identity (1.2).

Discrete and continuous master theorems. An additional feature of our interpolation-based

analysis is that we always work on the same real function f(x), which coincides with the

original sequence f(n)at integer parameters, unlike general master theorems that distinguish

between “discrete master theorems” and “continuous master theorems”; for example, according

to [33]:

To distinguish the two situations, we call the master theorem without ﬂoors and

ceilings the continuous master theorem and the master theorem with ﬂoors and

ceilings the discrete master theorem.

The subtleties of the two different versions (together with other issues) are only very recently

thoroughly examined in [33], where they write:

Several academic works provide proofs and proof sketches of the discrete master

theorem. To the best of our knowledge, however, all of these proofs are either

incomplete, incorrect, or require sophisticated mathematics.

See also the long paper (more than 300 pages) [4] for other delicate issues arising from

divide-and-conquer recurrences. Additionally, the chapter on “Recurrences” (Chapter I.4) in

the ﬁrst edition of Cormen et al.’s book [10] is now largely expanded and updated in the latest,

very recent, edition [11, Ch. I.4], more than three decades after its ﬁrst edition and following

the corresponding developments in clarifying the subtleties; see [4,11].

For more information and references on master theorems and divide-and-conquer recur-

rences, see, for example, [13,23,26,33,35]. See also [27] for more references on other

approaches (including complex-analytic, Tauberian, renewal, fractal geometry, and Ansatz or

guess-and-prove, called the substitution method in [11]) used in the literature for solving (1.1).

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Identitiesandperiodicoscillationsofdivide-and-conquerrecurrencessplittingathalf*Hsien-KueiHwangInstituteofStatisticalScience,AcademiaSinicaTaipei115TaiwanSvanteJansonDepartmentofMathematicsUppsalaUniversityUppsalaSwedenTsung-HsiTsaiInstituteofStatisticalScienceAcademiaSinicaTaipei115TaiwanFriday21st...

展开>> 收起<<

Identities and periodic oscillations of divide-and-conquer recurrences splitting at half Hsien-Kuei Hwang.pdf

共68页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Identities and periodic oscillations of divide-and-conquer recurrences splitting at half Hsien-Kuei Hwang

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: