Original Articles

On a Constant Arising in the Analysis of Bit Comparisons in Quickselect

Published in: Quaestiones Mathematicae
Volume 31 , issue 4 , 2008 , pages: 303–306

DOI: 10.2989/QM.2008.31.4.1.605

Author(s): PeterJ. Grabner , Helmut Prodinger

Keywords: BIT COMPARISONS , QUICKSELECT , RESIDUES , EULER-MACLAURIN FORMULA

Abstract

A (real) constant that appears as the factor of the leading term of the average number of bit comparisons required by quickselect, and was originally given in terms of complex numbers, is expressed using real numbers alone. A further representation is derived which is converging very quickly.

« Frame valued stratified generalized convergence groups

Joint Distributions for Movements of Elements in Sattolo's and the Fisher-Yates Algorithm »