2016/11/15 by Sumit Kumar Jha, Jha, Sumit Kumar
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Bayesian Methods and Mixture Models #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms
paper · pdf · doi:10.48550/arxiv.1611.04784
openalex publication_date 2016/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The in-situ permutation algorithm due to MacLeod replaces (x1,⋯,xn) by (xp(1),⋯,xp(n)) where π=(p(1),⋯,p(n)) is a permutation of \1,2,⋯,n\ using at most O(1) space. Kirshenhofer, Prodinger and Tichy have shown that the major cost incurred in the algorithm satisfies a recurrence similar to sequence of the number of key comparisons needed by the Quicksort algorithm to sort an array of n randomly permuted items. Further, Hwang has proved that the normalized cost converges in distribution. Here, following Neininger and Rüschendorf, we prove the that rate of convergence to be of the order Θ(ln(n)/n) in the Zolotarev metric.