Merge sort: differenze tra le versioni

Versione delle 11:23, 1 gen 2013

Versione delle 19:27, 27 gen 2013

Riga 92:

* la funzione merge qui presentata ha complessità temporale <math>\Theta(n)</math>

* mergesort richiama se stessa due volte, e ogni volta su (circa) metà della sequenza in input

Da questo segue che il tempo di esecuzione dell'algoritmo è dato dalla ricorrenza:

<math>T(n) = 2T\left(\frac{n}{2}\right)+ \Theta(n)</math>