title: Quickselect
text: # Quickselect
  
  In informatica, quickselect è un algoritmo randomizzato ricorsivo che trova il k-esimo elemento di un array disordinato di grandezza n eseguendo $O(n^2)$ confronti nel caso peggiore e O(n) nel caso atteso. Si basa sull'algoritmo Quicksort e sfrutta la metodologia prune and search.
  
  L'algoritmo quicksort ha diverse relazioni di ricorrenza, dovute al tipo di problema di minore entità che si viene a creare ogni volta che l'algoritmo viene eseguito. Se ogni chiamata ricorsiva dimezza il problema, si ha:
  
  $T(n)={\mathcal {O}}(n)+T\left({n \over 2}\right)$
  
  che ha soluzione O(n) in base al teorema master.
  
  Se invece si è nel caso peggiore, si ottiene: $T(n)={\mathcal {O}}(n)+T(n-1)$ che ha soluzione $O(n^2)$ in base al teorema master.
  
  