Open AccessBounds on Complexity when Sorting Reals
Publication year - 2020
Publication title -
international journal of circuits, systems and signal processing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.156
H-Index - 13
ISSN - 1998-4464
DOI - 10.46300/9106.2020.14.39
Subject(s) - sorting , sort , sorting algorithm , bounded function , mathematics , function (biology) , set (abstract data type) , time complexity , discrete mathematics , computational complexity theory , upper and lower bounds , computer science , algorithm , combinatorics , arithmetic , mathematical analysis , evolutionary biology , biology , programming language
We derive the upper bounds on the complexity of the counting sort algorithm applied to reals. We show that the algorithm has a time complexity O(n) for n data items distributed uniformly or exponentially. The proof is based on the fact that the use of comparison-type sorting for small portion of a given data set is bounded by a linear function of n. Some numerical demonstrations are discussed.