Analisi Algoritmi - Sostituzione

[hamming_burst]

Salve, vorrei chiedere una mano per capire la tecnica di sostituzione utilizzata nell'analisi degli algoritmi.
Mi sto trovando in difficoltà a capire alcuni passaggi, banali, ma fondamentali.

Preciso che non chiedo il Metodo di Sostituzione per dimostrare che un'equazione di ricorrenza appartiene ad una determinata classe di complessità (con induzione ecc)
Ma il metodo di risoluzione per sosituzione per risolvere le equazioni di ricorrenza, praticamente la prima parte per capire l'andamento di un'equazione.

Es: binary_search()

Equeazione di ricorrenza:

$T(n) = \{(c,n=1),(T(n/2) + d,n>1):}$

risoluzione per sostituzione

$T(n) = T(n/2) + d$
$= T(n/4) + 2d$
$= T(n/8) + 3d$
$. . .$
$= T(1) + kd$
$= T(0) + (k + 1)d$
$= kd + (c + d) = d log n + e$

Quello che non mi è chiaro è cosa accade alla funzione per passare da $T(n/2)+d$ a $T(n/4)+2d$
In questo esempio non si vede, ma c'è un'espansione in ogni passaggio sostituendo l'attuale T(n).

Circa avviene questo: $T(n/4)+2d -> ((T(n/2)+d)+d)$

è sbagliato, ma non capendolo non so riprodurre il passaggio. Essendo una funzione $T(n)$ come fà $n$ ad essere modificata?
Avevo capito il passaggio, ma ritrovare gli appunti è un casino.

Ringrazio moltissimo chi aiuta

EDIT:
Un esempio più chiaro di quello che chiedo:

Torre di Hanoi ricorsiva:

$T(n) = 1$ se $n=1$
$T(n) = 2T(n-1) + 1$ se $n>=2$

sostituendo successivamente:

$T(n) = 2T(n-1)+1$
$= 2 (2T(n-2)+1) + 1 = 4T(n-2)+3 = ....$
$.... = 2^(n-1) T(1) + 2^(n-1) -1 = 2^n - 1$

questo esempio aggiunge le sostituzioni ai passaggi,
a voi perpiacere spiegarmi cosa accade nei passaggi, che io proprio non li capisco o meglio c'è qualcosa che mi impedisce di vedere la soluzione. Grazie

[Rggb1]

"ham_burst":Un esempio più chiaro di quello che chiedo:

Torre di Hanoi ricorsiva:

$T(n) = 1$ se $n=1$
$T(n) = 2T(n-1) + 1$ se $n>=2$

sostituendo successivamente:

$T(n) = 2T(n-1)+1$
$= 2 (2T(n-2)+1) + 1 = 4T(n-2)+3 = ....$
$.... = 2^(n-1) T(1) + 2^(n-1) -1 = 2^n - 1$

questo esempio aggiunge le sostituzioni ai passaggi,

Esempio più chiaro e anche più semplice.
Se $T(n)=2T(n-1)+1$ per un generico $n$ maggiore di uno, allora
$T(n)=2*T(n-1)+1$ e quel $T(n-1)$ lo sostituisci con quanto vale $T(n)$ per un generico $n$ maggiore di uno, ovvero
$=2*(2*T(n-2)+1)+1=4*T(n-2)+3= ....$ eccetera.

Mi rendo conto che così è uguale a come l'hai scritta a parte che ho "separato" il 2, però puoi usare un altro modo: cambia nome alla variabile di ricorrenza (magari anche solo mentalmente)
$T(m)=2*T(m-1)+1$ e se $m=n-1$
$T(m)=2*T(n-2)+1$ e quindi
$T(n-1)=2*T(n-2)+1$
espressione che va sostituita.

Insomma si tratta sempre di un semplice passaggio algebrico; però anch'io spesso mi ci incarto

[hamming_burst]

Se T(n)=2T(n-1)+1 per un generico n maggiore di uno, allora
T(n)=2⋅T(n-1)+1 e quel T(n-1) lo sostituisci con quanto vale T(n) per un generico n maggiore di uno, ovvero
=2⋅(2⋅T(n-2)+1)+1=4⋅T(n-2)+3=.... eccetera.

Forse ci sono.

$T(n) = 2T(n-1)+1 = $
$T(n-1) = 2 (2T( (n-1) -1 ) +1) +1 $

ad ogni ricorsione il valore di $n$ viene modificato, e viene aggiunto al T(n) corrente, e le costanti della ricorsione precedente vengono aggiunte alla ricorsione attuale.
Spero sia così.

La cosa adesso che non mi è chiara, presupponendo che quello che ho scritto è corretto, la sostituzione di un'equazione è doppia allora. Nel senso che (matematicamente forse non ha senso):

messo che $2T(n-1)+1 = y$

Prima sostituzione è di tutta l'equazione ricorsiva $2(y)+1$ se espando $y$ in questo passaggio avrò una seconda sostituzione all'interno di $T(n)$ cioè $(n-1)-1$

E' corretto quello che ho scritto?

Se si, in un caso così applicando la sostituzione:

$T(n) = T(n/2) + T(n-1) +d$

$= (T((n/2)/2) + T((n-1)-1) + d)+d$
$= T(n/4) + T(n-2) + 2d $

corretto?

Intanto grazie

EDIT:
cambiato na cosa nella formula

[Rggb1]

"ham_burst":Forse ci sono.

$T(n) = 2T(n-1)+1 =
$T(n-1) = 2 (2T( (n-1) -1 ) +1) +1 $

No... (oppure non ho capito cosa hai fatto, che per me è lo stesso).

Ci riprovo. La tua $T(n)$ è definita per ricorsione su $n$ nel seguente modo, come hai scritto

$T(n)=1$ se $n=1$
$T(n)=2*T(n-1)+1$ se $n>=2$

Quindi
$T(n-1)=2*T(n-2)+1$
$T(n-2)=2*T(n-3)+1$
...
$T(2)=2*T(1)+1$
$T(1)=1$

Ora prova a vedere le sostituzioni, prendendo quello che ho scritto sopra
$T(n)=2*T(n-1)+1$ ma del resto sostituendo $T(n-1)$ ho
$T(n)=2*(2*T(n-2)+1)+1=4*T(n-2)+3$ e sostituendo $T(n-2)$ ancora ho
$T(n)=4*T(n-2)+3=4*(2*T(n-3)+1)+3=8*T(n-3)+7$ e proseguo
$T(n)=8*T(n-3)+7=8*(2*T(n-4)+1)+7=16*T(n-4)+15$ finche - è il caso - mi accorgo già che la formula ha una forma generale
$T(n)=2^(n-1)T(1)+2^(n-1)-1$ dove $T(1)=1$ e quindi $T(n)=2^n-1$

Puoi farla anche andando a incrementare, ma a volte questo metodo si ingarbuglia (vedi nel tuo primo esempio, se vuoi provare) oppure non sempre ti bastano pochi passaggi per trovare la forma generale:
$T(1)=1$
$T(2)=2*T(1)+1=3$ (che è $2^2-1$)
$T(3)=2*T(2)+1=2*(2*T(1)+1)+1=4*T(1)+3=7$ (che è $2^3-1$)
... eccetera.

PS. Mamma mia come è complicato farlo capire, decisamente non sono tagliato per insegnare
Comunque ti assicuro, una volta capito il meccanismo, il tutto è estremamente semplice.

[hamming_burst]

Fantastico, adesso mi son tolto il dubbio, mi è molto più chiaro. Come pensavo è banale la sostituzione in sè, è più complicato il calcolo finale e la relativa dimostrazione con induzione.
Devo allenarmi un po' con la tecnica di dimostrazione e beccare la giusta complessità da confrontare.

Ti ringrazio molto, mi hai tolto un problema