dc.contributor |
Centre de Recerca Matemàtica |
dc.contributor.author |
Martínez Parra, Conrado |
dc.contributor.author |
Panholzer, Alois |
dc.contributor.author |
Prodinger, Helmut |
dc.date.accessioned |
2010-04-06T09:28:46Z |
dc.date.available |
2010-04-06T09:28:46Z |
dc.date.created |
2009-11 |
dc.date.issued |
2009-11 |
dc.identifier.uri |
http://hdl.handle.net/2072/47982 |
dc.format.extent |
29 |
dc.format.extent |
253578 bytes |
dc.format.mimetype |
application/pdf |
dc.language.iso |
eng |
dc.publisher |
Centre de Recerca Matemàtica |
dc.relation.ispartofseries |
Prepublicacions del Centre de Recerca Matemàtica;901 |
dc.rights |
Aquest document està subjecte a una llicència d'ús de Creative Commons, amb la qual es permet copiar, distribuir i comunicar públicament l'obra sempre que se'n citin l'autor original, la universitat i el centre i no se'n faci cap ús comercial ni obra derivada, tal com queda estipulat en la llicència d'ús (http://creativecommons.org/licenses/by-nc-nd/2.5/es/) |
dc.subject.other |
Anàlisi combinatòria |
dc.title |
The analysis of approximate quickselect and related problems |
dc.type |
info:eu-repo/semantics/preprint |
dc.subject.udc |
519.1 - Teoria general de l'anàlisi combinatòria. Teoria de grafs |
dc.description.abstract |
Approximate Quickselect, a simple modification of the well known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Approximate Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm.
The key element appearing in the analysis of Approximate Quickselect is a trivariate
recurrence that we solve in full generality. The general solution of the recurrence
proves to be very useful, as it allows us to tackle several related problems, besides the
analysis that originally motivated us.
In particular, we have been able to carry out a precise analysis of the expected
number of moves of the ith element when selecting the jth smallest element with
standard Quickselect, where we are able to give both exact and asymptotic results.
Moreover, we can apply our general results to obtain exact and asymptotic results
for several parameters in binary search trees, namely the expected number of common
ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance
between the nodes of ranks i and j. |