soluzione in breve

Nel caso si abbia sempre $k=1$, allora otteniamo la ricorrenza

$$T_n = T_1 + T_{n-1} + \Theta(1) = T_{n-1} + \Theta(1)$$

Che ha soluzione $T(n)= \Theta(n)$.

Nel caso si abbia sempre $k=\lfloor\frac{n}{2}\rfloor$, allora otteniamo la ricorrenza

$$T_n = T_{\lfloor\frac{n}{2}\rfloor} + T_{\lceil\frac{n}{2}\rceil} + \Theta(\frac{n}{2})$$

Che ha soluzione $T(n)= \Theta(n\log n)$ (è la stessa ricorrenza che per il MergeSort), come si può dedurre dal Master Theorem, e verificare per induzione.

Vorremmo ora evidenziare che i due casi esaminati sono effettivamente due casi estremi (in senso asintotico, si vedano gli approfondimenti per un'analisi più sottile). Per fare ciò verificheremo che, comunque vengano scelti i valori di $k$, avremo $c_1 n \leq T_n \leq c_2 n \log_n$, per induzione. Prima di partire con le 2 verifiche formali ci conviene però osservare una volta per tutte che una definizione equivalente della $T_n$ è la seguente.

$$T_n = T_k + T_{n-k} + \Theta(k)$$   $$\mbox{\hspace{1cm} per $k\geq 1$, $k< \lfloor \frac{n}{2}\rfloor$}$$$$$$

Verifichiamo $T_n \geq c_1 n$, per induzione:

$$T_n = T_k + T_{n-k} + \Theta(k) \geq c_1 k + c_1 (n-k) + \Theta(k) \geq c_1 (k+n-k) = c_1 n$$

Verifichiamo $T_n \leq c_2 n\log_2 n$, per induzione:

$$T_n = T_k + T_{n-k} + \Theta(k) \leq c_2 k\log_2 k + c_2 (n-k)\log_2 (n-k) + \Theta(k) \leq c_2 k\log_2 k + c_2 (n-k)\log_2 n + \Theta(k)$$

$$= (c_2 k\log_2 n - c_2 k\log_2 \frac{n}{k})+ c_2 (n-k)\log_2 n +\Theta(k) \leq c_2 n\log_2 n - c_2 k\log_2 2 +\Theta(k)$$

$$= c_2 n\log_2 n - c_2 k +\Theta(k)$$

Resta pertanto induttivamente verificato che $T_n\leq c_2 n\log_2 n - c_2 k +\Theta(k) \leq c_2 n\log_2 n$ non appena la $c_2$ scelta sia sufficientemente grande da dominare la costante nascosta nella notazione $\Theta(k)$.