Average complexity of divide-and-conquer algorithms
type: Item
instance of: scholarly article
title: Average complexity of divide-and-conquer algorithms
zbMATH Open document ID: 0662.68038
DOI: 10.1016/0020-0190(88)90232-3
author: Boris S. Veroy
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: The goal of this paper is to describe a rather general approach for constructing upper and lower bounds for the average computational complexity of divide-and-conquer algorithms.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W99
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 4082969
zbMATH Keywords: unicrossing pair of functions
zbMATH Keywords: upper and lower bounds
zbMATH Keywords: average computational complexity
zbMATH Keywords: divide-and-conquer algorithms
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90232-3
OpenAlex ID: W2068131793
cites work: Q3898031
cites work: Average time analyses of simplified Davis-Putnam procedures
cites work: Q3835022
cites work: An algorithm to solve them ×n assignment problem in expected timeO(mn logn)
cites work: Q4057549
cites work: Q5569338
cites work: Q3919074
cites work: Combinatorial solutions of multidimensional divide-and-conquer recurrences
cites work: Expected-time complexity results for hierarchic clustering algorithms which use cluster centres
cites work: Q3967358
cites work: Q3346084
cites work: Q3673103
cites work: Average case optimality for linear problems
cites work: An optimal algorithm for search of extrema of a bimodal function
cites work: On the average speed of Lemke's algorithm for quadratic programming
cites work: Average case optimality
description: scientific article; zbMATH DE number 4082969