Fast Sorting of Weyl Sequences Using Comparisons | Zendy

Martin Ellis | Zendy; John Steele | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Fast Sorting of Weyl Sequences Using Comparisons

Author(s) -

Martin Ellis,

John Steele

Publication year - 1981

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0210007

Subject(s) - mathematics , irrational number , sorting , omega , alpha (finance) , combinatorics , algorithm , task (project management) , binary logarithm , sorting algorithm , discrete mathematics , statistics , geometry , construct validity , physics , management , quantum mechanics , economics , psychometrics

An algorithm is given which makes only $O(\log n)$ comparisons, and which will determine the ordering of the uniformly distributed (pseudo random) Weyl sequences given by $\{ (k\alpha )\bmod 1:1 \leqq k \leqq n\} $, where $\alpha $ is an unspecified irrational number. This result is shown to be best possible in the sense that no algorithm can perform the same task with fewer than $ \Omega (\log n)$ comparisons.

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