[ASD, Algoritmi] Risoluzione ricorrenze - metodo di sostituzione

[HackAlli]

Salve
Ho ripreso a studiare algoritmi e ho dei dubbi sui passaggi che vengono fatti durante la risoluzione di una ricorrenza mediante il metodo di sostituzione. Mi spiego meglio...
Data questa ricorrenza:
[tex]T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n[/tex]
Suppongo come soluzione [tex]O(n \lg n)[/tex]
Quindi per la definizione del metodo devo dimostrare che [tex]T(n) \leq cn\lg n[/tex] per un a[tex]c > 0[/tex]
Poi sul libro leggo "Supponiamo che questo limite sia valido per [tex]\lfloor n/2 \rfloor[/tex], ovvero che [tex]T(\lfloor\frac{n}{2}\rfloor) \leq c \lfloor\frac{n}{2} \rfloor \lg(\lfloor\frac{n}{2} \rfloor)[/tex]. Facendo le opportune sostituzioni nella ricorrenza, si ha"
[tex]T(n) \leq 2(c\lfloor\frac{n}{2}\rfloor\lg(\lfloor\frac{n}{2}\rfloor)) + n[/tex]
Mi mostrate quali sarebbero le opportune sostituzioni?

[apatriarca]

Ha semplicemente sostituito a T(n/2) l'espressione c(n/2)lg(n/2)..