Bounds on Complexity when Sorting Reals

0531334 - ÚI 2021 RIV US eng J - Článek v odborném periodiku
Jiřina, Marcel
Bounds on Complexity when Sorting Reals.
International Journal of Circuits, Systems and Signal Processing. Roč. 14, July (2020), s. 276-281. ISSN 1998-4464
Grant CEP: GA MŠMT LM2015068
Institucionální podpora: RVO:67985807
Klíčová slova: Linear time * Sorting reals * Time complexity
Obor OECD: Statistics and probability
Způsob publikování: Open access

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.
Trvalý link: http://hdl.handle.net/11104/0310011