BALANCING IS NOT ALWAYS GOOD
Original Publication Date: 1981-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Publishing Venue
Software Patent Institute
Related People
MARC SNIR: AUTHOR [+2]
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 -
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
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...