Dimostrazione su Relazione di ricorrenza

[leadfoot]

salve.
E' mai possibile che la realzione T(n)= 2T(n/2) + c sia O(n) ?
Perche a me viene sempre O(log n).

che ne dite?

[hamming_burst]

Ciao,
prova a calcolare la ricorrenza $T(n) = T(n/2) + c$ e dimmi cosa viene (con solito $\Theta(1)$ quando $n=1$).

[leadfoot]

ho capito.
non devo pensare ad n come se fosse la x di polinimio.

[hamming_burst]

"leadfoot":ho capito.
non devo pensare ad n come se fosse la x di polinimio.

che c'entra con questo?

prova a calcolare la ricorrenza. Cmq che tecnica utilizzi per far venir fuori $O(logn)$?

[leadfoot]

"hamming_burst":[quote="leadfoot"]ho capito.
non devo pensare ad n come se fosse la x di polinimio.

che c'entra con questo?

prova a calcolare la ricorrenza. Cmq che tecnica utilizzi per far venir fuori $O(logn)$?[/quote]
la ricorsiva.

[hamming_burst]

ok è il metodo algebrico.
Fai vedere almeno i calcoli che fai, almeno capiamo dove sbagli e possiamo dirti il perchè...

[leadfoot]

ok.
T(n)= T(n/2)+ c ;
T(n/2)= T(n/4)+ c;
T(n/4)=T(n/8)+c;

T(n)= c+c+c + T(n/2) + t(n/4)+T(n/8)
T(n)= 3c+ [T(n/2) + t(n/4)+T(n/8)]
t(n)= i c + T(n/2^i) ;

T(n)= c log n+1;
T(n)= O(log n)

[hamming_burst]

mi sembra ok.

perciò abbiamo calcolato $T(n/2) + c in O(log_2(n))$ che sarebbero la relazione di ricorrenza e la complessità della Binary Search

Ora fai lo stesso ragionamento e calcoli con $2T(n/2) + c$ è quasi identico.

[leadfoot]

forse ho capito dove sbaglio.
posso far sparire i 2 semplificandoli?
Se li semplifico però modifico il valore di n , e l'input non ha piu la taglia di origine.

[apatriarca]

Non puoi semplificare i due. Seguendo infatti il tuo procedimento dovrebbe comparire un \(2^{\log_2 n} = n\) da qualche parte..

[leadfoot]

T(n)=2T(n/2)+ c
la posso scrivere come
T(n)= T(n/2)+ T(n/2)+ c
T(n)= T(n/2)+ T(n/2)+ c + T(n/4)+ T(n/4)+ c
T(n)= 2c + [T(n/2) + T(n/2) + T(n/4)+ T(n/4)]
T(n)= ic + [T(n/2^i)+ T(n/2^1) ]
T(n)= ic + [log n + log n]
T(n)= ic + log n log n
T(n)= ic + 2^log n
T(n) = O(n) ????
è cosi?

[leadfoot]

non mi aiuta nessuno?

[apatriarca]

Per prima cosa cerca di usare le formule. La tua dimostrazione non è comunque corretta in quanto
\[ T(n) = 2\,T(n/2) + c \neq 2\,T(n/2) + 2\,T(n/4) + c. \]
Piuttosto il passaggio corretto è quello di osservare che
\[ T(n/2^i) = 2\,T(n/2^{i+1}) + c \]
per cui
\[ T(n) = 2\,T(n/2) + c = 2\,(2\,T(n/4) + c) + c = \dots = 2^i \, T(n/2^i) + c \, \sum_{k=0}^{i-1} \, 2^k = 2^i \, T(n/2^i) + (2^i - 1) \, c. \]
La ricorsione si ferma quando \( i = \log_2 n \) per cui
\[ T(n) = 2^{\log n} \, T(1) + (2^{\log n} - 1) \, c = n \, (T(1) + c) - c. \]

[leadfoot]

ora si.
davvero, Grazie.