Exact balancing is not always good (Q1072369): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q4773298 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Divide and conquer for linear expected time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recurrence relations based on minimization / rank | |||
Normal rank |
Latest revision as of 13:17, 17 June 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