Distributional convergence for the number of symbol comparisons used by QuickSelect

Details Distributional convergence for the number of symbol comparisons used by QuickSelect Distributional convergence for the number of symbol comparisons used by QuickSelect

2012-02-13

arxiv.org/abs/1202.2599v1

Mathematics

Probability

Scientific paper

When the search algorithm QuickSelect compares keys during its execution in order to find a key of target rank, it must operate on the keys' representations or internal structures, which were ignored by the previous studies that quantified the execution cost for the algorithm in terms of the number of required key comparisons. In this paper, we analyze running costs for the algorithm that take into account not only the number of key comparisons but also the cost of each key comparison. We suppose that keys are represented as sequences of symbols generated by various probabilistic sources and that QuickSelect operates on individual symbols in order to find the target key. We identify limiting distributions for the costs and derive integral and series expressions for the expectations of the limiting distributions. These expressions are used to recapture previously obtained results on the number of key comparisons required by the algorithm.

Affiliated with

Also associated with

No associations

Rating

Distributional convergence for the number of symbol comparisons used by QuickSelect does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distributional convergence for the number of symbol comparisons used by QuickSelect, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributional convergence for the number of symbol comparisons used by QuickSelect will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-680795