Sommatoria

[Lordofnazgul]

ciao a tutti ragazzi! ho un dubbio: ho svolto un esercizio di algoritmi e strutture dati I, sono arrivato al risultato finale (che è sostanzialmente $n + n + n + ......... + n$) solo che il libro dice che questa espressione deve essere asintotica a $nlgn$.
qualcuno ha una vaga idea di come potrei dimostrarlo?? perchè io pensavo che fosse semplicemente la sommatoria per n che va da zero a infinito di n, invece non è così...
(per $lgn$ intendo il logaritmo in base 2 di n).
Grazie mille!

[dissonance]

In genere per questo tipo di stime asintotiche torna utile il teorema di Stolz-Cesaro. E' analogo al teorema di l'Hôpital: se sai che $b_n \to +\infty$ ed è strettamente crescente (questa richiesta non ha analogo nella regola di l'Hôpital), allora se esiste

$lim_{n \to infty}\frac{a_{n+1}-a_n}{b_{n+1}-b_n}$

esiste anche

$lim_{n \to infty} \frac{a_n}{b_n}$

e i due limiti sono uguali. Nel tuo caso, devi calcolare

$lim_{n \to infty} \frac{n+n+...+n}{n log_2 n}$; prova a porre $a_n=n+n+...+n, b_n=n log_2 n$ e vedere cosa ottieni con il teorema di Stolz-Cesaro.

P.S.: Questo post starebbe meglio nella sezione di Analisi matematica.

[Lordofnazgul]

In genere per questo tipo di stime asintotiche torna utile il teorema di Stolz-Cesaro. E' analogo al teorema di l'Hôpital: se sai che $b_n \to +\infty$ ed è strettamente crescente (questa richiesta non ha analogo nella regola di l'Hôpital), allora se esiste

$lim_{n \to infty}\frac{a_{n+1}-a_n}{b_{n+1}-b_n}$

esiste anche

$lim_{n \to infty} \frac{a_n}{b_n}$

e i due limiti sono uguali. Nel tuo caso, devi calcolare

$lim_{n \to infty} \frac{n+n+...+n}{n log_2 n}$; prova a porre $a_n=n+n+...+n, b_n=n log_2 n$ e vedere cosa ottieni con il teorema di Stolz-Cesaro.

P.S.: Questo post starebbe meglio nella sezione di Analisi matematica.

grazie mille, questo teorema mi tornerà decisamente utile per altre verifiche che dovrò fare!
però il problema è che, io sapevo che l'espressione che avevo ricavato doveva essere asintotica a $nlgn$ perchè c'era scritto sul libro. Ma supponiamo che ero all'esame, e dovevo appunto trovare a cosa era asintotico $n + n + n + n + ............. +n$
come mi sarei dovuto comportare??

[Rigel]

Io avrei detto che $\sum_{i=1}^n n = n\cdot n = n^2$, ma forse ho capito male.
Se anche fosse $\sum_{i=1}^n i = n(n+1)/2$, sempre di $O(n^2)$ stiamo parlando.

[dissonance]

Ma supponiamo che ero all'esame, e dovevo appunto trovare a cosa era asintotico $n + n + n + n + ............. n$
come mi sarei dovuto comportare??

Occhio ai congiuntivi...

Purtroppo è un argomento che non conosco molto. Non credo ci siano strade standard però, la mia impressione è che si debba andare per tentativi. Ma aspettiamo l'opinione di qualcuno che ne capisce più di me.