T(n) = 3T(n/3) + 2n e T(0) = T(1) = T(2) = 4
Dopo aver studiato un po' (un po' poco a dire il vero), ho provato a scrivere la seguente soluzione:
Ipotiziamo T(n)=O(nlog(n))
Passo base: T(2)=4 <= c2log(2)=2c , se c>=2
Passo induttivo: T(n)=3T(n/3)+2n <= c3*n/3*log(n/3)+2n = cn(log(n) – log(3)) + 2n = cnlog(n)-cnlog(3)+2n <= cnlog(n) implica n(2-clog(3))<=0 implica c >= 2/log(3)
Da cui l’ipotesi
Potreste cortesemente verificare la (improbabile
) correttezza della soluzione, fornendomi eventualmente qualche spunto ?Grazie mille
