Equazione di ricorrenza

[Darèios89]

Mi sembra strano il mio pensiero, è sbagliata questa soluzione?

L' equazione è:

[tex]T(n)=T(n-2)+2\log(n)[/tex]

[tex]T(n)=\sum_{i=2}^{n}2\log(i)\leq n\log(n)[/tex]

[tex]T(n)=\theta(n\log(n))[/tex]

[hamming_burst]

si c'è un errore che io ho inglobato nella costante (che non si dovrebbe fare), ma essendo una limitazione asintotica è un qualcosa di ordine inferiore $n$ aggiunto alla costante non cambia assolutamente nulla. Ma per essere corretti serve introdurre una piccola cosa alla dimostrazione, te la scrive meglio un altro momento. Sottolineo però che è corretto il procedimento, solo che c'è un fattore che non corrisponde alla dimostrazione corretta, ti spiegherò pure come risolvere questi inconvenienti, è sempre utile.

Intanto, la dimostrazione che è $Theta(n)$ è banale e non ha sotterfugi nascosti, viene semplicemente, basta che segui i procedementi che ti ho scritto.

[hamming_burst]

Allora, anche se non serve, a me non piace lasciare le cose incomplete, perciò ti mostro come risolvere questi inconvenienti.
Riassumiamo la situazione, noi vogliamo dimostrare che:

$T(n) = 2T(n/3) + 2T(n/9) + n in O(n^(log_3(4)))$

l'ultima parte della dimostrazione è:

$(5/8)cn^(log_3(4)) + n <= cn^(log_3(4))$

L’ipotesi è corretta tuttavia sottraiamo un valore di ordine inferiore.

per ovviare a ciò abbiamo bisogno di un'ipotesi più forte, perciò:

$T(n) = 2T(n/3) + 2T(n/9) + n <= c(n^(log_3(4)) - n)$ da notare che $n^(log_3(4)) - n in O(n^(log_3(4)))$

$2c((n/3)^(log_3(4)) - n/3)+ 2c((n/9)^(log_3(4)) - n/9) + n = 1/2cn^(log_3(4)) - 1/3cn + 1/8cn^(log_3(4)) - 1/9cn + n =$

$= 5/8cn^(log_3(4)) - 4/9cn + n <= cn^(log_3(4)) - 4/9cn + n <= cn^(log_3(4)) - cn$

l'ultima disequazione è vera se e solo se:

$cn^(log_3(4)) - 4/9cn + n <= cn^(log_3(4)) - cn$

$-4/9cn + n <= - cn$

$-4/9cn -cn <= -n$

$-5/9cn <= -n$

$5/9c >= 1$

$c >= 9/5$

con questo abbiamo dimostrato che $T(n) = 2T(n/3) + 2T(n/9) + n in O(n^(log_3(4)))$ per $c >= 9/5$ (il caso base lo ho lasciato da parte ma è subito dimostrato).

spero sia utile, questi accorgimenti servono ad evitare dimostrazioni farlocche ed errori "gravi"