Bounds on Complexity when Sorting Reals

Number of the records: 1

1.

SYSNO ASEP	0531334
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve SCOPUS
Title	Bounds on Complexity when Sorting Reals
Author(s)	Jiřina, Marcel (UIVT-O)_{SAI, RID}
Source Title	International Journal of Circuits, Systems and Signal Processing. - : North Atlantic University Union - ISSN 1998-4464 Roč. 14, July (2020), s. 276-281
Number of pages	6 s.
Publication form	Online - E
Language	eng - English
Country	US - United States
Keywords	Linear time ; Sorting reals ; Time complexity
Subject RIV	BB - Applied Statistics, Operational Research
OECD category	Statistics and probability
R&D Projects	LM2015068 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
Method of publishing	Open access
Institutional support	UIVT-O - RVO:67985807
EID SCOPUS	85087528484
DOI	10.46300/9106.2020.14.39
Annotation	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.
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2021
Electronic address	http://hdl.handle.net/11104/0310011

Number of the records: 1