Problemino con il Teorema Master

[Darèios89]

Ho questa equazione di ricorrenza:

[tex]T(n)=4T(n/2)+n^2\sqrt{n}[/tex]

Credo si possa risolvere con il terzo caso del teorema Master, cioè ho che:

[tex]f(n)=\Omega(n^{2+\epsilon})[/tex] per [tex]\epsilon=\frac{1}{2}[/tex] dovrebbe essere vera.

Il problema è che dovrei verificare la condizione di regolarità, ma non riesco....cioè dovrei verificare che:

[tex]af(n/b)\leq cf(n)[/tex] per n sufficientemente grande e per c<1.

Avrei se non sbaglio:

[tex]4[(\frac{n}{2})^\frac{5}{2}]\leq cn^{\frac{5}{2}}[/tex]

Scrivendo il 4 in funzione della potenza di due l' ho semplificato con le proprietà delle potenze con il due a denominatore ottenendo:

[tex]\frac{n^{\frac{5}{2}}}{\sqrt{2}}\leq cn^{\frac{5}{2}}[/tex]

Ho sbagliato?

[hamming_burst]

ok corretto

ultimo passaggio baste che togli fuori $n^(5/2)$ e avrai la condizione $c$.

[Darèios89]

Mh....quindi...forse scegliendo [tex]c=\frac{1}{\sqrt{2}}[/tex]

Per c minore o uguale a quel valore è vera la disugualgianza?

Grazie mille in anticipo...non so come farei senza di te..

[hamming_burst]

mmm, non mi sembra che il teorema dice esplicitamente che deve essere $c <=$ di qualcosa. Esattamente ricordo che $c<1$ per essere vera la limitazione, perciò se $c = 1/sqrt(2) < 1$ è vera, ma non deve essere a sual volta di $c<=$ di qualcosa. Devi trovare un solo valore degli infiniti $<1$ che faccia verificare la condizione. ok?


lieto di essere d'aiuto

[Darèios89]

Ti ringrazio tanto!!