Exact balancing is not always good (Q1072369): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0020-0190(86)90148-1 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2079755555 / rank | |||
Normal rank | |||
Revision as of 00:59, 20 March 2024
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
