sommatoria semplice che non so fare

[Giova411]

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

[@melia]

La sommatoria è una serie geometrica e vale $1/(1-1/2)= 2$

[Giova411]

Grazie Amelia!

Quindi posso proseguire così?

$\ cn * 2 - b(log n) + 1 <= cn - b $

Sono un po' insicuro...

[Giova411]

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!!!

[vict85]

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.

[@melia]

Perdono, non mi ero accorta che partiva da 1, ho visto la serie geometrica e sono partita in quarta!

[Giova411]

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:

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

[vict85]

In effetti hai ragione, mi viene il segno meno davanti al \(log_2 n\). Comunque non vengo spesso in questa sezione.

[Giova411]

Grazie VicT sei un Drago anche qui!
Gli altri "ragionamenti" sono esatti? Di come mi muovo con le sommatorie dico...

[Fioravante Patrone]

Ancora su questi aridi lidi?
Un abbraccio
F