I keep seeing proofs for the linear expected running time.of Quickselect which use the fact that for each recursive call there is a 50% chance that the array is split in subarrays of at least 25% and at most 75% of the initial array size - proof bases on phases. However, this fact is really false: for a size of 3: we get 1/3 and also for odd sizes in general. I also have a little dillema whether 25-75 includes the boundaries, since in the case of a size of, say, 8, if the bounds are included, we get 5/8 as the probability..
I'd really appreciate a clarification on the bounds and a hint on how the runnning time proof can be fixed when we consider the fact that the probability of passing to a next phase is not 50% (which invalidates a fair coin-flip analogy).
Aucun commentaire:
Enregistrer un commentaire