DOAJ
Open Access
2012
Exact $L^2$-Distance from the Limit for QuickSort Key Comparisons (Extended Abstract)
Patrick Bindjeme
james Allen fill
Abstrak
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}$.
Topik & Kata Kunci
Penulis (2)
P
Patrick Bindjeme
j
james Allen fill
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2012
- Sumber Database
- DOAJ
- DOI
- 10.46298/dmtcs.3003
- Akses
- Open Access ✓