Average complexity of divide-and-conquer algorithms

DOI10.1016/0020-0190(88)90232-3zbMath0662.68038OpenAlexW2068131793MaRDI QIDQ1114395

Boris S. Veroy

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90232-3

zbMATH Keywords

upper and lower boundsaverage computational complexitydivide-and-conquer algorithmsunicrossing pair of functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Algorithms in computer science (68W99)

Related Items (3)

Average complexity of divide-and-conquer algorithms ⋮ Optimal search algorithm for a minimum of a discrete periodic bimodal function ⋮ Optimal search algorithm for extrema of a discrete periodic bimodal function

Cites Work

• Average time analyses of simplified Davis-Putnam procedures
• Average case optimality for linear problems
• Average case optimality
• Average complexity of divide-and-conquer algorithms
• An optimal algorithm for search of extrema of a bimodal function
• Expected-time complexity results for hierarchic clustering algorithms which use cluster centres
• Combinatorial solutions of multidimensional divide-and-conquer recurrences
• An algorithm to solve them ×n assignment problem in expected timeO(mn logn)
• On the average speed of Lemke's algorithm for quadratic programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Average complexity of divide-and-conquer algorithms