[Algoritmi]Risoluzione ricorrenza al variare di un parametro
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))$
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))$