[Algoritmi]Ricorrenza Metodo Di Sostituzione

[oxidojack]

ciao a tutti
mi sto preparando per l'esame di algoritmi e
non riesco a capire come risolvere le ricorrenze con il metodo di sostituzione..
per esempio mi potete spiegare senza saltare i passi queste ricorrenza?

T(n) = 2T([N/2]) + N

Grazie mille

[Giova411]

Grazie Hamming!!!
Buona giornata a tutti!!!!

[HackAlli]

Ho letto la discussione perchè anche io non ci sto a capire niente e sono arrivato a delle conclusioni e correggetemi se sbaglio
In pratica usiamo come ipotesi induttiva che T(n)<= c n lg n
E definiamo come passo induttivo qualcosa di più forte di T(n) ,cioè supponiamo che se è vera T(n)<= cnlgn allora lo sarà anche qualcosa che è più piccolo di T(n) e in questo caso T(n/2) <= c(n/2)lg(n/2)
(bene ora non ho capito perchè sostituiamo e in che modo e dove sostituiamo)