Algoritmi

[sara09]

Buonasera mi aiutate a risolvere questo esercizio di algoritmi e strutture dati?


La sommatoria non ha forma chiusa quindi non so come fare a dimostrare se è vera o meno
Grazie in anticipo

[apatriarca]

Credo che una strategia possa essere quella di considerare l'integrale (lo puoi risolvere facilmente per parti)
\[ \int_1^n (\log_2\,x)^2 dx \]

[sara09]

Credo che una strategia possa essere quella di considerare l'integrale (lo puoi risolvere facilmente per parti)
\[ \int_1^n (\log_2\,x)^2 dx \]

Ok ma poi il risultato di questo integrale posso fare il limite del rapporto tra il risultato del integrale e F(n)=(nlogn)^2 in base a risultato capisco se è theta o omega oppure o-grande?
Oppure non posso calcolarmi il limite di n che tende ad infinito della funzione della sommatoria e poi fare il limite del rapporto è in base al risultato verifi se è theta o meno?

[apatriarca]

Non è necessario fare il limite avendo a che fare con funzioni che sai già come si comportano asintoticamente e la loro relazione. Hai quindi
\[
\begin{align*}
\int_1^n (\log_2\,x)^2 dx &= \frac{n\,(\log\,n)^2 - 2\,n\,\log_2\,n + 2\,n - 2}{(\log\,2)^2} \\
&= n\,(\log_2\,n)^2 + o\bigl(n(\log_2\,n)^2\bigr) \in \Omega\bigl(n\,(\log_2\,n)^2\bigr)
\end{align*}\]
A questo punto non rimane altro che dimostrare che questo integrale e la tua serie hanno lo stesso comportamento asintotico. Suppongo che mostrare che
\[ \int_1^{n-1} (\log_2\,x)^2 dx < \sum_{i=1}^n (\log_2\,n)^2 < \int_1^n (\log_2\,x)^2 dx \]
sia sufficiente.

[sara09]

Non è necessario fare il limite avendo a che fare con funzioni che sai già come si comportano asintoticamente e la loro relazione. Hai quindi
\[
\begin{align*}
\int_1^n (\log_2\,x)^2 dx &= \frac{n\,(\log\,n)^2 - 2\,n\,\log_2\,n + 2\,n - 2}{(\log\,2)^2} \\
&= n\,(\log_2\,n)^2 + o\bigl(n(\log_2\,n)^2\bigr) \in \Omega\bigl(n\,(\log_2\,n)^2\bigr)
\end{align*}\]
A questo punto non rimane altro che dimostrare che questo integrale e la tua serie hanno lo stesso comportamento asintotico. Suppongo che mostrare che
\[ \int_1^{n-1} (\log_2\,x)^2 dx < \sum_{i=1}^n (\log_2\,n)^2 < \int_1^n (\log_2\,x)^2 dx \]
sia sufficiente.

Capito potresti spiegarmi solo come hai calcolato l’integrale perché purtroppo il mio esami di analisi questa parte non c’era....si calcola allo stesso modo degli integrali definiti tra due numeri?