Exact balancing is not always good (Q1072369)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Exact balancing is not always good |
scientific article |
Statements
Exact balancing is not always good (English)
0 references
1986
0 references
The following recurrence relation frequently occurs in the analysis of divide-and-conquer algorithms: \[ M_ f(0)=0,\quad M_ f(n+1)=f(n+1)+\min_{i+j=n}(M_ f(i)+M_ f(j)). \] In these applications, f is the cost of merging two subproblems, wereas \(M_ f(i)\) and \(M_ f(j)\) are the costs of solving each subproblem; f is monotonic nondecreasing. In this paper we consider such recurrences, when f is not assumed to be convex.
0 references
balanced trees
0 references
optimization problem on binary trees
0 references
analysis of divide- and-conquer algorithms
0 references
merging
0 references