Bounds on Complexity when Sorting Reals | Zendy

Marcel Jiřina | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Bounds on Complexity when Sorting Reals

Author(s) -

Marcel Jiřina

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research