Studiando il QuickSelect (aka RANDOMIZED-SELECT) da questo libro: https://people.mpi-inf.mpg.de/~mehlhorn ... oolbox.pdf
non sono riuscito a capire l'analisi al caso medio (pagina 115, Teorema 19).
In particolare mi sfugge il senso della disequazione
$ T(n) <= cn + \gammaT(2n/3) + (1 - \gamma)T(n) $
dove $ \gamma $ indica la probabilità per un pivot di essere un 'buon pivot'. Secondo la teoria un pivot è detto buon pivot se, quando viene pescato all'interno dell'array in modo casuale (con la subroutine in versione random di Parition, utilizzata da Quicksort), il pivot cade nel terzo centrale (ovvero, supposto di aver suddiviso l'array in tre parti 'uguali', per terzo centrale si intende la parte di mezzo). Non riesco proprio a capire il senso di quella disequazione e come essa possa limitare inferiormente la relazione di ricorrenza.
Il prof scrisse una versione analoga di quella disequazione, ovvero l'equazione seguente:
$ T(n) = \theta(n) + 1/3 T(2n/3) + 2/3T(n-1) $
dove si è esplicitato il valore della probailità $ \gamma $.
Per una maggiore comprensione fornisco anche il codice:
