Equazione di ricorrenza

[juvedelpiero]

Ragazzi non riesco a capire come fare per vedere se una funzione è un O(..). Sul mio libro ho un esempio ma non riesco a capire come lui imposta la disequazione. L'esercizio è dimostrare che:

$ T(n)=3T(n/4)+Theta (n^2) $ sia un $ O(n^2) $

Il libro dice "intendiamo dimostrare che $ T(n)<=dn^2 $ per qualche costante $ d>0 $ :

$ T(n)<= 3T(n/4)+cn^2 $
$ <=3d(n/4)^2+cn^2 $
$ =3/16dn^2+cn^2 $
$ <=dn^2 $

"vera finché $ d>=(16/13) $

Potete spiegarmi il procedimento di questi passaggi, grazie

[BoG3]

Provo a risponderti io ma ... prendila con le pinze, vediamo se sparo cavolate mio correggeranno:)

"juvedelpiero":Ragazzi non riesco a capire come fare per vedere se una funzione è un O(..). Sul mio libro ho un esempio ma non riesco a capire come lui imposta la disequazione. L'esercizio è dimostrare che:

$ T(n)=3T(n/4)+Theta (n^2) $ sia un $ O(n^2) $

Il libro dice "intendiamo dimostrare che $ T(n)<=dn^2 $ per qualche costante $ d>0 $ :

So che ad ogni iterazione ho un costo pari a $Theta(n^2)$ e da quello non si scappa.

$ T(n)<= 3T(n/4)+cn^2 $

Proprio perchè ho supposto (tento di indovinare, grazie alla mia esperienza, all'occhio o una palla maginca, non so...) che la mia ricorrenza è limitata superiormente da $dn^2$ e quindi ho sostituito al posto di $T$ la sua stima "a tentativi" fatta sopra (appunto: $dn^2$). Metto il $<=$ proprio perchè ho supposto che la mia stima sia maggiore o uguale al costo effettivo della funzione:

$ <=3d(n/4)^2+cn^2 $
$ =3/16dn^2+cn^2 $
$ <=dn^2 $

Il resto sono calcoli algebrici per ricavarsi $d$ ossia: $ d>=(16/13) $

Spero di non aver sparato cavolate.
PS: io comunque avrei tentato con un $d*n^2 logn$