Some Results on Asymptotic Behavior of the Recalls of Random Median Quicksort
نویسندگان
1 Department of Statistics, University of Zanjan, Zanjan, I. R. Iran
2 Department of Statistics, University of Zanjan, Zanjan, I. R. Iran
doi
10.22052/mir.2022.246282.1347چکیده
This paper investigates the asymptotic behavior of the number of recalls Xn of the Random Median Quicksort algorithm in order to sort a list of n distinct numbers. As n→∞, we provide the asymptotics of the expectation and variance of the recalls. Furthermore, by utilizing a refined version of the contraction method for degenerate limits, we show the limiting distribution of Xn correctly normalized is Gaussian. The theoretical results are demonstrated by a simulation study.
