Sommatoria semplice che non so fare
Ragazzi vi chiedo una mano che mi serve per uno studio di complessità di algoritmi.
$\sum_{i=1}^(log n) ((cn)/2^i - b) + 1 <= cn - b $
Il tutto considerando numeri naturali e $c>0, b>0$ e logaritmo $log_2$, io ho provato ad arrivare a:
$\ cn * sum_{i=1}^(log n) (1/2^i) - b(log n) + 1 <= cn - b $
Per $n$ che tende ad infinito che puo' succedere?
$\ cn * sum_{i=1}^(oo) (1/2^i) - b(log n) + 1 <= cn - b $
la sommatoria tende a zero ma non arrivo alla soluzione esatta 
$\sum_{i=1}^(log n) ((cn)/2^i - b) + 1 <= cn - b $
Il tutto considerando numeri naturali e $c>0, b>0$ e logaritmo $log_2$, io ho provato ad arrivare a:
$\ cn * sum_{i=1}^(log n) (1/2^i) - b(log n) + 1 <= cn - b $
Per $n$ che tende ad infinito che puo' succedere?
$\ cn * sum_{i=1}^(oo) (1/2^i) - b(log n) + 1 <= cn - b $
la sommatoria tende a zero ma non arrivo alla soluzione esatta
Risposte
La sommatoria è una serie geometrica e vale $1/(1-1/2)= 2$
Grazie Amelia!
Quindi posso proseguire così?
$\ cn * 2 - b(log n) + 1 <= cn - b $
Sono un po' insicuro...
Quindi posso proseguire così?
$\ cn * 2 - b(log n) + 1 <= cn - b $
Sono un po' insicuro...
Fatto sta che al mio Prof viene $b>=(1)/(1+log_2 n)$ valida per ogni $c$
Ma non ho idea di come arrivi qui PERBACCO!!!
Ma non ho idea di come arrivi qui PERBACCO!!!
Sei arrivato a \(\displaystyle 2cn - b\log_2 n + 1 \le cn - b \).
A questo punto
\(\displaystyle \begin{align} 2cn - b\log_2 n + 1 &\le cn - b \\
b(1 - \log_2 n) &\le 1 - cn \\
b \ge \frac{1-cn}{1-\log_2 n}
\end{align} \)
dove l'ultimo passaggio è legato al fatto che \(\displaystyle \log_2 n > 1 \) per \(\displaystyle n>2 \). Che è comunque diverso da quello che viene al professore.
Questo succede perché la somma geometrica citata da @melia parte da 0 mentre la tua parte da 1. Quindi in realtà si ha \(\displaystyle cn - b\log_2 n + 1 \le cn - b \) che si riduce alla stessa cosa del professore.
A questo punto
\(\displaystyle \begin{align} 2cn - b\log_2 n + 1 &\le cn - b \\
b(1 - \log_2 n) &\le 1 - cn \\
b \ge \frac{1-cn}{1-\log_2 n}
\end{align} \)
dove l'ultimo passaggio è legato al fatto che \(\displaystyle \log_2 n > 1 \) per \(\displaystyle n>2 \). Che è comunque diverso da quello che viene al professore.
Questo succede perché la somma geometrica citata da @melia parte da 0 mentre la tua parte da 1. Quindi in realtà si ha \(\displaystyle cn - b\log_2 n + 1 \le cn - b \) che si riduce alla stessa cosa del professore.
Perdono, non mi ero accorta che partiva da 1, ho visto la serie geometrica e sono partita in quarta!
Amelia io ho solo da dirti grazie!!!
Vic sei sempre tu?!?!?!! Mi salvi il bagigio anche in questa sezione?!?!??!?!
Straight to the point perché non mi è chiaro.. Parto da:
$\sum_{i=1}^(log n) ((cn)/2^i - b) + 1 <= cn - b $
Tolgo fuori il $- b$ e lo moltiplico per il limite massimo che raggiunge la sommatoria.
Ok? fermatemi se sbaglio
(sì, come alle scuole elementari!)
$\ cn * sum_{i=1}^(log n) (1/2^i) - b(log n) + 1 <= cn - b $
Ora vado a prendermi le serie notevoli. Come diceva Amelia è una geometrica ma, come diceva Vic mi parte da 1 e non zero!!
Qui non so muovermi bene!
$\ sum_{i=1}^(log n) (1/2)^i = ((1/2) ^1 - (1/2)^(log n +1))/(1-1/2)$ che è $==>1$
PS:
Se fosse partita da zero sarebbe andata così?
$\ sum_{i=0}^(log n) (1/2)^i = (1- (1/2)^(log n +1))/(1-1/2)$
Quello che mi dava fastidio era $(1/2)^(log n +1)$ che con $n$ che tende ad $oo$ tende a $0$ Esatto?
PS2:
A me non viene come al Prof. lo stesso
Vic sei sempre tu?!?!?!! Mi salvi il bagigio anche in questa sezione?!?!??!?!
Straight to the point perché non mi è chiaro.. Parto da:
$\sum_{i=1}^(log n) ((cn)/2^i - b) + 1 <= cn - b $
Tolgo fuori il $- b$ e lo moltiplico per il limite massimo che raggiunge la sommatoria.
Ok? fermatemi se sbaglio
(sì, come alle scuole elementari!)$\ cn * sum_{i=1}^(log n) (1/2^i) - b(log n) + 1 <= cn - b $
Ora vado a prendermi le serie notevoli. Come diceva Amelia è una geometrica ma, come diceva Vic mi parte da 1 e non zero!!
Qui non so muovermi bene!
$\ sum_{i=1}^(log n) (1/2)^i = ((1/2) ^1 - (1/2)^(log n +1))/(1-1/2)$
che è $==>1$PS:
Se fosse partita da zero sarebbe andata così?
$\ sum_{i=0}^(log n) (1/2)^i = (1- (1/2)^(log n +1))/(1-1/2)$
Quello che mi dava fastidio era $(1/2)^(log n +1)$ che con $n$ che tende ad $oo$ tende a $0$ Esatto?
PS2:
"vict85":
Quindi in realtà si ha \(\displaystyle cn - b\log_2 n + 1 \le cn - b \) che si riduce alla stessa cosa del professore.
A me non viene come al Prof. lo stesso
In effetti hai ragione, mi viene il segno meno davanti al \(log_2 n\). Comunque non vengo spesso in questa sezione.
Grazie VicT sei un Drago anche qui!
Gli altri "ragionamenti" sono esatti? Di come mi muovo con le sommatorie dico...
Gli altri "ragionamenti" sono esatti? Di come mi muovo con le sommatorie dico...
Ancora su questi aridi lidi?
Un abbraccio
F
Un abbraccio
F
"Fioravante Patrone":
Ancora su questi aridi lidi?
Un abbraccio
F
Sì Prof!!!! AHAHHAHAHAHAH
-caduto dalla sedia-
Signori e Signori colui il quale insieme a Luca Barletta e Camillo mi hanno aiutato tantissimo con analisi2 e calcolo delle prob!!!
Mamma che bei tempi!!!!
Poi ho lavorato 7 anni lasciando un esame ad aspettarMI....
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo