$T(n)=sqrt(n)T(sqrt(n))+n$
$T(n)=sqrt(n)T(sqrt(n))+n$
Ho posto $ n = 2^m$ quindi $m = log_2 n$
$T(2^m) = sqrt(2^m) T(sqrt(2^m)) + 2^m$
$S(m) = T(2^m) = m/2 S(m/2) + m $
Pensavo di usare il Master ma
Ho posto $ n = 2^m$ quindi $m = log_2 n$
$T(2^m) = sqrt(2^m) T(sqrt(2^m)) + 2^m$
$S(m) = T(2^m) = m/2 S(m/2) + m $
Pensavo di usare il Master ma
Risposte
Apa come sempre grazie!
Certo che me li scelgo proprio "adatti a me" sti esercizi.......
Dovrebbe essere un $ Theta(nloglogn)$ stando agli appunti...
Certo che me li scelgo proprio "adatti a me" sti esercizi.......
Dovrebbe essere un $ Theta(nloglogn)$ stando agli appunti...
Ho cancellato il messaggio quasi subito dopo averlo scritto perché mi ero accorto di un errore. Non è in particolare esatto il tuo ultimo passaggio.
Se valgono
\[ S(m) = T(2^m) \quad \text{e} \quad T(2^m) = 2^{m/2}\,T(2^{m/2}) + 2^m\]
allora avrai che
\[ S(m) = 2^{m/2}\,S(m/2) + 2^m \neq (m/2)\,S(m/2) + m/2\]
come invece hai scritto nel tuo primo post.
Se valgono
\[ S(m) = T(2^m) \quad \text{e} \quad T(2^m) = 2^{m/2}\,T(2^{m/2}) + 2^m\]
allora avrai che
\[ S(m) = 2^{m/2}\,S(m/2) + 2^m \neq (m/2)\,S(m/2) + m/2\]
come invece hai scritto nel tuo primo post.
Sì ti ho portato nel vortice degli errori poi!!! PARDON!!!
Per un attimo ho intravisto la soluzione ma .... rimane un po' inedita come ricorrenza...
PS: sulla carta avevo scritto due elevato un mezzo per m...... che disastro sono....
Per un attimo ho intravisto la soluzione ma .... rimane un po' inedita come ricorrenza...
PS: sulla carta avevo scritto due elevato un mezzo per m...... che disastro sono....
Vabò vado a fare una corsetta per liberare la capoccia... 
Per caso si potrebbe arrivare ad avere una sorta di serie armonica come mi facesti vedere un paio di giorni fa?
tipo $\sum_{i=1}^{\log_2(n)} \frac{1}{2^i}$
Per caso si potrebbe arrivare ad avere una sorta di serie armonica come mi facesti vedere un paio di giorni fa?
tipo $\sum_{i=1}^{\log_2(n)} \frac{1}{2^i}$
Se dividiamo tutto per $2^m$ abbiamo:
$(T(2^m) )/ s^m = (T(2^(m/2)))/2^(m/2) + (m/2)/(2^m) $
Poi se poniamo $S(w) = (T(2^m)) /(2^m) $ possiamo arrivare a :
$S(w) = S(w/2) +$
$(T(2^m) )/ s^m = (T(2^(m/2)))/2^(m/2) + (m/2)/(2^m) $
Poi se poniamo $S(w) = (T(2^m)) /(2^m) $ possiamo arrivare a :
$S(w) = S(w/2) +$
dai un occhio a questo. è circa la stessa cosa scritta da apatriarca, ma con qualche passaggio in più.
La parte più a destra non la devo considerare proprio? 
Forse arrivo a definire O grande con una certa soddisfazione
Ma per arrivare ad Omega ragazzi..... Immagino sia un BRASILE-GERMANIA(*)
(*) io giocherei in porta nel Brasile... ed in una squadra piccolina in Canadà con tanti fiori di lillà!
Forse arrivo a definire O grande con una certa soddisfazione
Ma per arrivare ad Omega ragazzi..... Immagino sia un BRASILE-GERMANIA(*)
(*) io giocherei in porta nel Brasile... ed in una squadra piccolina in Canadà con tanti fiori di lillà!
Un giorno lontano lontano spero di essere un apatriarchino o hamming_burstino anch'io 
Eccomi miei cari PersonalProf 
$T(n)=sqrt(n)T(sqrt(n))+n$
Poniamo $ n = 2^m$ quindi vale anche $m = log_2 n$
(a quanto ho capito usiamo, quando ci fa comodo, o l'una o l'altra. Vero Ham?
)
$T(2^m) = sqrt(2^m) T(sqrt(2^m)) + 2^m == 2^(1/2m) T(2^(1/2m)) + 2^m == 2^(m/2) T(2^(m/2)) + 2^m$ oki
Se dividiamo tutto per $2^m$ abbiamo:
$(T(2^m) )/ 2^m = (T(2^(m/2)))/2^(m/2) + (2^m)/(2^m) $
Un inciso per la parte più a dx: prima anche arrivavamo, ma di fortuna, ad ottenere un $theta(1)$ : mi riferisco al post dove scrivevo, in modo errato, $ (m/2)/(2^m) $ perchè questa parte tendeva a zero al tendere di m verso l'infinito ed oltre... Ma era sbagliato!
$(T(2^m) )/ 2^m = (T(2^(m/2)))/2^(m/2) + theta(1) $ si può vedere tutto in modo più semplice ponendo $(T(2^m) )/ 2^m = S(m)$
$S(m) = S(m/2) + theta(1) $
Andiamo di M T, che è stato ideato per semplificare le cose, MA NO! NOI NON LE VOGLIAMO SEMPLICI!!!
OK... Ora lo possiamo usare per avere che $S(m) = theta(log m) $ magicamente ma non abbiamo i diritti per farlo già da subito...
$S(m) = O(log m) $ si perché $S(m) <= S(m/2) + O(1) $ e dobbiamo rimettere insieme i pezzi.
$(T(2^m) )/ 2^m = O(log m) $
$T(2^m) = O(log m) *2^m $
ma ricordiamo il principio, quello che avevamo all'inizio:
$T(n) = O(log log n)n = O(nlog log n)$
Attendo conferme
Per il limite inferiore abbandono la barca! Si puo' vedere ad occhio un'omega di n...
$T(n)=sqrt(n)T(sqrt(n))+n$
Poniamo $ n = 2^m$ quindi vale anche $m = log_2 n$
(a quanto ho capito usiamo, quando ci fa comodo, o l'una o l'altra. Vero Ham?
)$T(2^m) = sqrt(2^m) T(sqrt(2^m)) + 2^m == 2^(1/2m) T(2^(1/2m)) + 2^m == 2^(m/2) T(2^(m/2)) + 2^m$ oki
Se dividiamo tutto per $2^m$ abbiamo:
$(T(2^m) )/ 2^m = (T(2^(m/2)))/2^(m/2) + (2^m)/(2^m) $
Un inciso per la parte più a dx: prima anche arrivavamo, ma di fortuna, ad ottenere un $theta(1)$ : mi riferisco al post dove scrivevo, in modo errato, $ (m/2)/(2^m) $ perchè questa parte tendeva a zero al tendere di m verso l'infinito ed oltre... Ma era sbagliato!
$(T(2^m) )/ 2^m = (T(2^(m/2)))/2^(m/2) + theta(1) $ si può vedere tutto in modo più semplice ponendo $(T(2^m) )/ 2^m = S(m)$
$S(m) = S(m/2) + theta(1) $
Andiamo di M T, che è stato ideato per semplificare le cose, MA NO! NOI NON LE VOGLIAMO SEMPLICI!!!
OK... Ora lo possiamo usare per avere che $S(m) = theta(log m) $ magicamente ma non abbiamo i diritti per farlo già da subito...
$S(m) = O(log m) $ si perché $S(m) <= S(m/2) + O(1) $ e dobbiamo rimettere insieme i pezzi.$(T(2^m) )/ 2^m = O(log m) $
$T(2^m) = O(log m) *2^m $
ma ricordiamo il principio, quello che avevamo all'inizio:
$T(n) = O(log log n)n = O(nlog log n)$
Attendo conferme
Per il limite inferiore abbandono la barca! Si puo' vedere ad occhio un'omega di n...
$T(n) = sqrt(n) T(sqrt(n)) + n $
Dovrebbe essere banale $T(n) = Omega(n)$ cioé esiste un $c>0, m>=0 : T(n)>=cn$ per ogni $n>=m$?
Passo base: $T(1) = 2 >= c*1$ sì, per $c<=2$
Passo induttivo:
$T(n) = sqrt(n) T(sqrt(n)) + n $
$ >= sqrt(n) c(sqrt(n)) + n $
$ = cn + n >= cn$ sì per $c<=1, n>= 0$
Forse ho confuso le costanti
Ma non era questo il limite inferiore stretto...
Come si potrebbe fare?
$T(n) = sqrt(n) T(sqrt(n)) + n $
$T(n) >= c(n log(logn)) $ ?
quindi
$sqrt(n) *c*(sqrt(n) loglog(sqrt(n))) + n$
Dovrebbe essere banale $T(n) = Omega(n)$ cioé esiste un $c>0, m>=0 : T(n)>=cn$ per ogni $n>=m$?
Passo base: $T(1) = 2 >= c*1$ sì, per $c<=2$
Passo induttivo:
$T(n) = sqrt(n) T(sqrt(n)) + n $
$ >= sqrt(n) c(sqrt(n)) + n $
$ = cn + n >= cn$ sì per $c<=1, n>= 0$
Forse ho confuso le costanti Ma non era questo il limite inferiore stretto...
Come si potrebbe fare?
$T(n) = sqrt(n) T(sqrt(n)) + n $
$T(n) >= c(n log(logn)) $ ?
quindi
$sqrt(n) *c*(sqrt(n) loglog(sqrt(n))) + n$
"Giova411":
Andiamo di M T, che è stato ideato per semplificare le cose, MA NO! NOI NON LE VOGLIAMO SEMPLICI!!!
OK... Ora lo possiamo usare per avere che $S(m) = theta(log m) $ magicamente ma non abbiamo i diritti per farlo già da subito...
Aggiornamenti dall'Alto!!!
In teoria va già bene così: limite superiore ed inferiore grazie al Master. Il resto è in più a quanto ho capito.
Quindi $ theta(n log log n) $
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo