Potete dimostrare che il merge sort ha una complessità temporale [math]O(n \log n)[/math]?

Fase di divisione

Lasciamo che ci sia un array di n elementi ... merge sort, essendo una relazione di ricorsività di tipo divide et impera, tende a prendere l'array e a dividerlo in 2 sub array di uguale dimensione (cioè sub array contenenti n/2 elementi per un array di n elementi) ricorsivamente fino a quando i sub array contengono solo 1 elemento.

Questa procedura di divisione richiede quindi D(n)=2D(n/2) tempo---> n è diviso in 2 sub-array di n/2 elementi.

Fase di conquista

Nella fase di conquista i primi elementi di ogni sub-array sono confrontati tra loro e l'elemento più piccolo è messo come primo elemento dell'array padre. Poi il precedente secondo elemento di un array diventa il suo elemento primario e viene confrontato con il primo elemento del secondo array. Questo processo richiede n-1 confronti in tutto, poiché l'ultimo elemento non deve essere confrontato.

This conquer procedure, hence, takes C(n) = n-1

Divide and Conquer

In total divide and conquer, thus, takes T(n)= D(n) + C(n) => T(n) = 2T(n/2) + n-1 => T(n) = 2T(n/2) + O(n)

Akra-Bazzi solution to the recurrence relation:

T(n)=2T(n/2) + n is a divide and conquer relation

where a = 2; b = 1/2;

Hence,

Step 1: we set p such that a*(b)^p = 1 => 2*(1/2)^1 = 1

Step 2: Plug p = 1 and g(u)=g(n)=n in: T(n) = θ(n + n ∫(n/n*n)du)
=> T(n) = θ(n + n∫(1/n)du) => T(n) = θ(n + n(lg n))

=> T(n) = θ ( n lg n)

Q.E.D.