[Algoritmi]Risoluzione ricorrenza al variare di un parametro

HeroGian
Apro questo topic perchè ho svolto diverse ricorrenze col teorema master, ma purtroppo il prof non ci ha dato le soluzioni dei problemi, quindi volevo chiedere a voi se va bene come ho risolto l'esercizio..

Studiare il comportamento di T(n) al variare del parametro $alpha > 0$

$T(n) = {(1,if n < 3),(4T(n/3)+2n^(alpha+1),if n >= 3):}$

- Primo caso Teorema dell'Esperto
se $2n^(alpha+1) in O(n^(log_3 4 - epsilon))$
Applico la definizione di limite superiore $2n^(alpha+1) <= cn^(log_3 4 - epsilon)$ con $c = 2, epsilon > 0$
$1+alpha <= log_3 4 - epsilon$
quindi per $alpha <= log_3 4 - epsilon -1 rArr T(n) in Theta(n^(log_3 4))$

- Secondo caso Teorema dell'Esperto
se $2n^(1+alpha) in Theta(n^(log_3 4))$
Applico la definizione di Limite stretto $c_1n^(log_3 4) <= 2n^(1+alpha) <= c_2n^(log_3 4)$
Per $c_1 = c_2 = 2 rArr log_3 4 <= 1+alpha <= log_3 4$
Quindi per $alpha = log_3 4 -1 rArr T(n) in Theta(n^(log_3 4)logn)$

- Terzo caso Teorema dell'Esperto
se $2n^(1+alpha) in Omega(n^(log_3 4 + epsilon))$
Applico la definizione di Limite Inferiore $2n^(1+alpha) >= cn^(log_3 4 + epsilon)$
Per $c = 2 rArr 1+alpha >= log_3 4 +epsilon rArr alpha >= log_3 4 +epsilon -1$
e se per qualche $c < 1$ risulta $af(n/b) <= cf(n)$
$4((2n^(1+alpha))/3) <= 2cn^(1+alpha)$ Risulta vera per $c = 4/3$
Quindi per $alpha >= log_3 4 -1 + epsilon rArr T(n) in Theta(2n^(1+alpha))$

Risposte
HeroGian
nessuno? :(

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.