Geodesic
Exact $L^2$-Distance from the Limit for QuickSort Key Comparisons (Extended Abstract)
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012).

Voir la notice de l'article provenant de la source Episciences

Using a recursive approach, we obtain a simple exact expression for the $L^2$-distance from the limit in the classical limit theorem of Régnier (1989) for the number of key comparisons required by $\texttt{QuickSort}$. A previous study by Fill and Janson (2002) using a similar approach found that the $d_2$-distance is of order between $n^{-1} \log{n}$ and $n^{-1/2}$, and another by Neininger and Ruschendorf (2002) found that the Zolotarev $\zeta _3$-distance is of exact order $n^{-1} \log{n}$. Our expression reveals that the $L^2$-distance is asymptotically equivalent to $(2 n^{-1} \ln{n})^{1/2}$. 
@article{DMTCS_2012_special_262_a24,
     author = {Bindjeme, Patrick and fill, james Allen},
     title = {Exact $L^2${-Distance} from the {Limit} for {QuickSort} {Key} {Comparisons} {(Extended} {Abstract)}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)},
     year = {2012},
     doi = {10.46298/dmtcs.3003},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3003/}
}
TY  - JOUR
AU  - Bindjeme, Patrick
AU  - fill, james Allen
TI  - Exact $L^2$-Distance from the Limit for QuickSort Key Comparisons (Extended Abstract)
JO  - Discrete mathematics & theoretical computer science
PY  - 2012
VL  - DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3003/
DO  - 10.46298/dmtcs.3003
LA  - en
ID  - DMTCS_2012_special_262_a24
ER  - 
%0 Journal Article
%A Bindjeme, Patrick
%A fill, james Allen
%T Exact $L^2$-Distance from the Limit for QuickSort Key Comparisons (Extended Abstract)
%J Discrete mathematics & theoretical computer science
%D 2012
%V DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3003/
%R 10.46298/dmtcs.3003
%G en
%F DMTCS_2012_special_262_a24
Bindjeme, Patrick; fill, james Allen. Exact $L^2$-Distance from the Limit for QuickSort Key Comparisons (Extended Abstract). Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012). doi : 10.46298/dmtcs.3003. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3003/

Cité par Sources :