[ASD] Metodo Sostituzione - Induzione

[lebrac]

Ciao, mi sto preparando all'esame di algoritmi e ho alcuni dubbi:

I dubbi riguardano il metodo di sostituzione e la successiva dimostrazione per induzione.

Prendo l'equazione di ricorrenza $ T(n) = 3T(n/4) + Theta (n^2) $

ottengo che il costo sia $ O(n^2) $ tramite ilmetodo dell'albero della ricorsione. E ho quindi la mia ipotesi

Quindi $ T(n) <= dn^2 $ per un $ d>0 $

$ T(n) <= 3T(n/4) + cn^2 $
$ <= 3d(n/4)^2 +cn^2 $
$ = 3/16 dn^2 +cn^2 $
$ <= dn^2 $ solo se $ d>= 16/13c $

Il punto è che qui mi fermo: non so cosa devo fare ora...
Non capisco a livello concettuale a cosa giungo e cosa mi manca. Cioè, ora ho dimostrato che per un certo d, vale l'ipotesi che avevo ottenuto con l'albero.

Spero di aver rispettato le regole postando quello che ho capito fin qui.
Qualcuno può aiutarmi?

EDIT:

Procedo con il caso base dell'induzione

$ n=1 $

$ T(1) = 3*1/4 + 1^2 = 7/4 $

$ T(n) <= dn^2 $
$ T(n) <= d $

ma io di $ d $ so solo che $ d>= 16/13c $ e che $ c>0 $

Io prima avevo usato d perchè avevo già usato c nell'equazione di ricorrenza...come proseguo?

[Giova411]

Speriamo qualcuno risponda che interessa anche me!

[lebrac]

Beh io ormai ho l'esame domani quindi mi rispondo da solo:

IPOTESI

$ T(n) in O(n^2) $

$ EE a >0 $ e $ EE bar(n) > 0 $ e $ AA n>bar(n) $

$ T(n) <= dn^2 $

$ bar(n) = 1 $

$ T(1) = a $ poi $ T(n) <= abar(n)^2 $

$ T(1) <= d*1 $ e quindi $ a<= d $

quindi

$ T(n) <= dn^2 AA n
passo induttivo

$ T(m) <= dm^2 $
$ T(m) = 3T(m/4) +cm^2 <= dm^2 $

$ 3d(m/4)^2 +cm^2 <= dm^2 $

facendo un paio di conti

$ d>= 16/13c $

che è quello ottenuto prima.

Attenzione alla differenza tra il caso base dell'equazione che è $ n=1 $ e il caso base dell'induzione che è $ bar(n) = 1 $ e che in altri esercizi può essere 2 o 3 etc... (nel caso 1 non vada bene, cioè ti venga una disequazione falsa, es $ d<0 $ ovvero un costo negativo che non può essere)

Ciao