Merge sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 181:
- la funzione merge ha costo Θ(n), e mergesort richiama se stessa due volte ogni volta su metà della porzione di input. Quindi possiamo associare al tempo di esecuzione di mergesort la funzione temporale
T(n) = 2T(n/2)+ Θ(n)
che per il secondo caso del teorema master è Θ(nlogn).
| |||