[Algoritmi] Metodo di sostituzione

[HeroGian]

Salve a tutti, sto svolgendo alcuni esercizi sulle ricorrenze, in particolar modo col metodo di sostituzione..
Ho provato a svolgere il seguente esercizio, ma purtroppo mi viene diverso dalla soluzione del prof e non riesco a capire dove sbaglio

$T(n)={(1,if n = 1),(text{n+2T(n/2)},if n > 1):}$

dimostro che $EE c > 0 : 0 <= T(n) <= cnlog(n) AA n > N$

caso Base:
per $n=1 -> T(1) = 1$
$0 <= 1 <= cnlog(n)$
$0 <= 1 <= clog(1)$ Falsa

Passo Induttivo:
$0 <= T(n) <= cnlog(n)$
$0 <= n+2c(n/2)log(n/2) <= cnlog(n)$
$n+cnlog(n/2) <= cnlog(n)$
$n+cnlog(n/2) - cnlog(n) <= 0$
$n+cn(log(n/2) - log(n)) <= 0$
$n+cn(log(n/2 /n)) <= 0$
$n+cn(log(1/2)) <= 0$
$cn >= n -> c >= 1 $

[apatriarca]

Per prima cosa il tuo passo base è sbagliato. Come tu stesso hai notato la relazione non vale per \(n = 1.\) Considera quindi almeno \(n = 2\) per cui si ha \( T(2) = 2 + 2\,T(1) = 4 \le c \, \log_2(2) = c. \) Per il resto puoi supporre che \(c\) sia maggiore o uguale a \(4\) e poi proseguire come hai scritto e ti viene corretto..

[HeroGian]

Ok credo di aver capito, in pratica vuol dire che per n < 2 la ricorrenza non vale nlog(n) mentre per n >= 2 si.. o sbaglio??

[hamming_burst]

come hai fatto i passaggi, anche se forse corretti, non sono esplicativi, perchè non espliciti cosa vuoi dimostrare:

$2c(n/2)log_2(n/2) + n = cnlog_2(n/2) + n = cn(log_2(n) - 1) + n =$
$= cnlog_2(n) - cn + n <= cnlog_2(n)$ per $c>=1$