Merge sort: differenze tra le versioni

Versione delle 17:14, 25 giu 2006

Versione delle 15:32, 10 lug 2006

Riga 177:

Il tempo di esecuzione dell'algoritmo Merge Sort è Θ(nlogn). Infatti:

- la funzione merge ha costo Θ(n), e mergesort richiama sesé stessa due volte ogni volta su metà della porzione di input. Quindi possiamo associare al tempo di esecuzione di mergesort la funzione temporale

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