[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))$

[HeroGian]

nessuno?