metodo dei limiti asintotici delle somme

Se non è possibile determinare l’asintotica di una somma usando il metodo della forma chiusa e il metodo dell’integrale, allora si procede stimando lo scenario peggiore (notazione O-grande) e quello migliore (notazione Omega): se sono uguali, allora si è ricavato anche lo scenario medio (notazione Theta).

esempio

Consideriamo la somma ${\sum }_{i=1}^{n}i$

caso peggiore

$\left({\sum }_{i=1}^{n}i\le {\sum }_{i=1}^{n}n\right)\wedge \left({\sum }_{i=1}^{n}n\in O(n^2)\right)⟹{\sum }_{i=1}^{n}i\in O(n^2)$

caso migliore

$\left({\sum }_{i=1}^{n}i\ge {\sum }_{i=\frac{n}{2}}^{n}i\ge {\sum }_{i=\frac{n}{2}}^n\frac{n}{2}=\frac{n}{2}{\sum }_{i=\frac{n}{2}}^{n}1=\frac{n}{2}\left(n-\frac{n}{2}\right)+1\approx \frac{n}{2}\cdot \frac{n}{2}=\frac{n^2}{4}\right)\wedge \left(\frac{n^2}{4}\in \Theta (n^2)\right)⟹{\sum }_{i=1}^{n}i\in \Theta (n^2$

caso medio

$S_n\in O(n^2)\wedge S_n\in \Omega (n^2)⟹S_n\in \Theta (n^2)$