Homogeneous and non-homogeneous algorithms

DOI10.1007/978-1-4614-5134-1_17MaRDI QIDQ4596168zbMATH OpenOpenAlexFDO

Authors Ioannis Paparrizos

Publication date 30 November 2017

Published in Optimization Theory, Decision Making, and Operations Research Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.3546

zbMATH Keywords

algorithm analysisalgorithm classificationalgorithm complexity

Mathematics Subject Classification ID

General topics in the theory of algorithms (68W01) Analysis of algorithms (68W40)

Abstract: Motivated by recent best case analyses for some sorting algorithms and based on the type of complexity we partition the algorithms into two classes: homogeneous and non homogeneous algorithms. Although both classes contain algorithms with worst and best cases, homogeneous algorithms behave uniformly on all instances. This partition clarifies in a completely mathematical way the previously mentioned terms and reveals that in classifying an algorithm as homogeneous or not best case analysis is equally important with worst case analysis.

Recommendations

• scientific article; zbMATH DE number 3876613
• Precision complexity analysis: A case study using insertion sort
• A note on the complexity of a partition algorithm
• Algorithms – ESA 2004
• scientific article; zbMATH DE number 3963207

Cites work

• Best case lower bounds for heapsort
• Homogeneous and non-homogeneous algorithms
• scientific article; zbMATH DE number 1629827 (Why is no real title available?)
• scientific article; zbMATH DE number 3909741 (Why is no real title available?)
• Implementing HEAPSORT with ( n log n - 0.9 n ) and QUICKSORT with ( n
• On the Best Case of Heapsort
• Precision complexity analysis: A case study using insertion sort
• Quicksort
• The Analysis of Heapsort
• Time bounds for selection
• Weak-heap sort

Cited in

(4)

• Precision complexity analysis: A case study using insertion sort
• scientific article; zbMATH DE number 3876613 (Why is no real title available?)
• scientific article; zbMATH DE number 3963207 (Why is no real title available?)
• Homogeneous and non-homogeneous algorithms

This page was built for publication: Homogeneous and non-homogeneous algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4596168)