Number of the records: 1
Bounds on Complexity when Sorting Reals
- 1.0531334 - ÚI 2021 RIV US eng J - Journal Article
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
R&D Projects: GA MŠMT LM2015068
Institutional support: RVO:67985807
Keywords : Linear time * Sorting reals * Time complexity
OECD category: Statistics and probability
Method of publishing: 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.
Permanent Link: http://hdl.handle.net/11104/0310011
File Download Size Commentary Version Access 0531334-aoa.pdf 6 905.7 KB OA CC BY 4.0 Publisher’s postprint open-access
Number of the records: 1