Merge sort: differenze tra le versioni

Versione delle 16:39, 11 giu 2006

Versione delle 17:32, 11 giu 2006

Riga 177:

- 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)

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

che per il secondo caso del teorema master è Θ(nlogn).

che per il secondo caso del teorema master è Θ(nlogn''n''log''n'').

[[de:Mergesort]]