approfondimenti

Sia $T(n) = T(n-k) + T(k) + \Theta(\min(k, n-k)).$ Questa ricorrenza non si può in generale risolvere con il Master Theorem. Bisogna quindi indovinare qualitativamente la soluzione e poi verificare per sostituzione diretta.

Ovviamente concediamo che $k$ sia una funzione di $n,$ $k= k(n).$ Supponiamo, senza perdita di generalità, che sia $k \leq n-k.$ Un caso estremo che può capitare è quello in cui $k= n/2$ (lasciamo perdere in prima approssimazione gli arrotondamenti). Qui otteniamo $T(n)= 2 T(n/2) + \Theta(n)$ che è la ricorrenza di mergesort, dunque con soluzione $T(n) \in \Theta(n \log n).$ L'altro caso estremo è quello in cui $k$ sia costante, ad esempio $k=1.$ In tal caso, essendo $T(k)= T(1)= \Theta(1),$ abbiamo $T(n)= T(n-1)+ \Theta(1)$ che ovviamente ha la soluzione $T(n) = \Theta(n).$

Per il caso generale $1 < k < n/2,$ intuiamo che l'andamento sia un qualcosa di intermedio tra questi due. Vediamo di formalizzare questa intuizione, per farlo in maniera pulita mettiamo in chiaro che cosa significa avere il $\Theta()$ entro la ricorrenza, e perchè non abbiamo specificato una condizione iniziale, ad esempio, su $T(1).$

Con maggiore dettaglio, la ricorrenza di sopra si potrebbe scrivere, sempre supponendo $k(n) \leq n/2,$

$$T(n) \geq T(k(n)) + T(n - k(n)) + \alpha k(n)$$

$$T(n) \leq T(k(n)) + T(n - k(n)) + \beta k(n)$$

$$T(1) = \gamma$$

per opportune costanti $\alpha > 0, \beta >0 , \gamma > 0.$ Notare che potremmo avere anche $\gamma =0;$ in tal caso meglio calcolarsi i primi $T(p)$ finchè non sia $T(p) > 0,$ e usare quella come condizione iniziale. Supponiamo comunque per ora, senza perdita di generalità, che sia $p=1.$ A questo punto, per ottenere un limite superiore ci interesseremo alla seconda ed alla terza riga; studiando la ricorrenza

$$S(n) = S(k(n)) + S(n - k(n)) + k(n), S(1)=1$$

è facile vedere che $T(n) \leq \max(\beta, \gamma) S(n).$ Per il limite inferiore, analogamente, ci interesseremo alla prima e terza riga; in questo caso avremo $T(n) \geq \min(\alpha, \gamma) S(n).$ Per questo possiamo supporre che tutte le costanti coinvolte siano pari a uno, e studiare la ricorrenza scritta sopra per $S(n).$ È facile rendersi conto che deve essere $S(n) \geq n;$ essendo $k(n) \geq 1,$ infatti,

$$S(n) \geq S(n - k(n)) + k(n)$$

(abbiamo addirittura trascurato un termine positivo); con la condizione iniziale data, è facile dimostrare la tesi per induzione.

Più complesso è dimostrare la limitazione superiore.