Browse Prior Art Database

BALANCING IS NOT ALWAYS GOOD

IP.com Disclosure Number: IPCOM000128180D
Original Publication Date: 1981-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 10 page(s) / 26K

Publishing Venue

Software Patent Institute

Related People

MARC SNIR: AUTHOR [+3]

Abstract

Recurrence formulas arising from the analysis of divide and conquer algorithms are considered. It is shown that the balancing principle is not always valid. General solutions and error estimates are provided.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 24% of the total text.

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

BALANCING IS NOT ALWAYS GOOD

BY MARC SNIR June 1981 Report No. 033 s

This work is based upon work supported in part by the U.S. Department of Energy Contract No. DE--AC02-'7.bER03077.

Abstract:

Recurrence formulas arising from the analysis of divide and conquer algorithms are considered. It is shown that the balancing principle is not always valid. General solutions and error estimates are provided.

Keywords: Algorithm analysis, Divide and conquer. - 1 -

1. Introduction

The time complexity of divide and conquer algorithms is often determined from a recurrence relation of the form

(Equation Omitted)

is the time required to solve two subproblems of size i and j respectively, and f(n) is the time needed to combine these two solutions. Typical examples are merge-sort (f (n)=0(n)) and maximum finding (f

(Equation Omitted)

. When analyzing such problems it is always assumed implicitly that an optimal solution to 1.1 is obtained by taking subproblems of equal sizes; This is the famous "Balancing Principle" [1, 2.3]. The recurrence 1.1 is therefore replaced by the recurrence

(Equation Omitted)

The next step is to solve the functional equations

(Equation Omitted)

and use the solution as an approximation to the correct solution of 1.2. We elaborate in this paper on each of these steps.

,r First, under what conditions is the Balancing Principle valid? It turns out that it is valid whenever the function f is convex. However, if f is concave an optimal solution to 1.1 is obtained by "unbalancing" as much as possible. The problem turns out to be related to that of building binary trees of minimal sum, where "tree sum" is defined to be a generalization of the external path length function. - 2 -

New York University Page 1 Dec 31, 1981

Page 2 of 10

BALANCING IS NOT ALWAYS GOOD

Next, we suggest a simple analytic formula to bound the error involved in using a solution to system 1.3 as an approxima-tion to the solution of system 1.2. Finally, we give a general solution to the system 1.3. Our results validates the usual analysis of the recurrence relation
1.1, for convex f. When f is concave, and therefore sublinear, the solution to 1.1 is 0(n), and (un)balancing optimally rather than evenly only affects the constant implicit in the 0 notation.

2. Optimal Splitting Definitions:

The first order difference of a function f(n) is defined to be

(Equation Omitted)

the k-th order difference is defined as

(Equation Omitted)

A function f is nondecreasing if Af > 0, nonincreasing if

(Equation Omitted)

. Note that if f(x) is k times differentiable and

(Equation Omitted)

. Functions f occuring in recurrence relations of the form 1.1, which describe the time complexity of divide and conquer algorithms, can be expected to be nonnegative and nondecreasing. Generally, they also will be convex, by a law of diminishing returns: the amount of work required to handle and extra item does not decrease as the...