Quicksort: complessità

• Caso ottimo: (vettore disordinato)

  • T(n)=2T((n-1)/2)+Pn

• Caso pessimo: (vettore ordinato)

  • T(n)=T(n-1)+Pn

• Caso medio:

  • nlog2n

Notes: