1° Appello - 01/01/2020 - Domanda 3

Esercizio 3

immagine

T(1)=1
T(N)= 2T(\frac{N}{2})+2
ricavo T(\frac{N}{2}) sostituendo (\frac{N}{2}) in T(N)
T(\frac{N}{2})= 2(\frac{N}{4})+2
sostutuisco T(\frac{N}{2}) così trovato in T(N)
T(N)= 2T(2(\frac{N}{4})+2)+2 = 4T(\frac{N}{4})+2+4
Dopo un numero i di passi
T(N)= 2^iT(\frac{N}{2^i})+\sum_{k=1}^{i}2^k
Pongo T(\frac{N}{2^i})= T(1)\Rightarrow \frac{N}{2^i}=1\Rightarrow i =\log_{2}{N}
sostituisco i in T(N)
T(N)= 2^{\log_{2}{N}} T(\frac{N}{2^{\log_{2}{N} }})+\sum_{k=1}^{\log_{2}{N} }2^k = N T(1)+\sum_{k=1}^{\log_{2}{N} }2^k
O(T(N))=O(N)+O(N)=O(2N)=O(N)
[ O\sum_{k=1}^{\log_{2}{N} }2^k é un O del suo termine di grado maggiore O(2^{\log_{2}{N} })=O(N) ]

1 Mi Piace