Ricorrenza, soluzione corretta?

[Darèios89]

[tex]T(n)=T(n/3)+\frac{n}{2}[/tex]

Ho provato ad indovinare se [tex]T(n)=O(n)[/tex]

[tex]T(n)\leq c\frac{n}{3}+\frac{n}{2}[/tex]

[tex]T(n)\leq \frac{2cn+3n}{6}[/tex]

[tex]T(n)\leq c(5n)[/tex]

Così.....per [tex]c\geq 1[/tex] è vera l' uguaglianza?

Qualcosa mi fa sospettare di no.....anche se in teoria assomiglia molto alla forma dell' ipotesi induttiva.

[Deckard1]

Perché sei saltato a $T(n) <= 5cn$? In questo modo ovviamente l'ipotesi induttiva non viene dimostrata, però:
$T(n) <= (2cn + 3n)/6 = 1/3 cn + 1/2n = (1/3c + 1/2)n <=cn$ per $c >=1$.
Maggiorare le equazioni per semplificare i calcoli è cosa buona e giusta, occhio però che se usi l'induzione a volte una maggiorazione di troppo può farti saltare la dimostrazione.

[Darèios89]

Ah...si, mi era venuto spontaneo fare il minimo comune multiplo, ovviamente la tua disuguaglianza è verificata per [tex]c\geq 1[/tex] ma se io scrivessi:

[tex]\frac{1}{3}c+\frac{1}{2}\leq c[/tex]

Che avrebbe soluzione [tex]c\geq \frac{3}{4}[/tex] mi porterebbe ad un valore errato di c per l' induzione?

[Deckard1]

$c$ è una costante qualsiasi: se in qualche passaggio della tua dimostrazione ottieni che $c$ deve essere almeno pari ad un certo valore non importa; ad es: $c>=10$ implica che il tepo di calcolo deve essere almeno $T(n)=10n$, che va benissimo perché sei interessato a dimostrare la linearità del tempo di calcolo, il valore della costante non ti interessa. Il problema è se cerchi di dimostrare che $T(n)<=cn$ e ottieni qualcosa come $T(n)=2cn$. In questo caso l'induzione non funziona più perché $T(n)=2cn>cn$. Per lo stesso motivo se nel passaggio induttivo dimostri che $T(n)<=5cn$ in realtà non hai dimostrato che $T(n)<=cn$ e quindi l'induzione crolla.

[Darèios89]

Ok, ti ringrazio tanto.