Espressioni asintotiche

[Larios1]

Salve,

Vorrei arrivare a dimostare per esempio semplici relazioni del tipo $f(n)=O(g(n))$:

$5n^2 + n = O(n^2)$
$3n^4 = O(n^5)$
$n log n = O(n^2)$
$log^k n = O(e^n)$

mi è chiaro teoricamente il fatto che $f(n)<= c * g(n)$ ma non riesco a capire quali sono i passaggi necessari per giungere all soluzione.

Se avete sotto mano una guida esaustiva tanto meglio, perchè non ho trovato molto materiale a riguardo non avendo niente sui miei libri...


Grazie

[Luca.Lussardi]

Una condizione che ti assicura quello che hai scritto è che $\lim_{n \to +\infty}(f(n))/(g(n))=c$ per una certa costante $c>0$. Il calcolo di tale limite negli esempi considerati dovrebbe esserti agevole.

Più in generale il limite va sostituito con il limsup, quella è la definizione di O.

[zorn1]

"Luca.Lussardi":Una condizione che ti assicura quello che hai scritto è che $\lim_{n \to +\infty}(f(n))/(g(n))=c$ per una certa costante $c>0$. Il calcolo di tale limite negli esempi considerati dovrebbe esserti agevole.

Più in generale il limite va sostituito con il limsup, quella è la definizione di O.

Davvero? Perché limsup, Luca? Non lo sapevo questo... anche se penso che continui a rimanere una relazione di equivalenza così, ma perché per esempio non liminf, oppure una media aritmetica tra liminf e limsup?

[Luca.Lussardi]

Date $f$ e $g$ positive esiste $c>0$ tale per cui definitivamente si ha $f(n) \leq c g(n)$ se e solo se limsup$(f(n))/(g(n)) \in (0,+\infty)$; la dimostrazione è elementare.

[Larios1]

dato $2n^2 + 3n + 1 <= c * n^2$ sapendo a priori che $O(n^2)$ e volendone verificare la correttezza ho operato nel seguente modo...

semplifico e togliendo l' $n^2$ a destra ottenendo

$2 + 3/n + 1/n^2 <= c $

sapendo che 2n^2 > 3n per $n > 1$ dunque testo per $n=2$ la parte sopra

ottengo

$2 + 3/n + 1/n^2=15/4$ prendero 4 perche $c ∈ N$

e questo è corretto




Ma se avessi avuto solo $2n^2 + 3n + 1$ e mi venisse chiesto di trovarne l' O grande avrei qualche difficolta nella dimostrarazione:

si comincia nell' isolare $n^2$ ottnenedo $n^2 + (3/2)n + 1/2$

Si ha $(3/2)n + (1/2) ≤ n2$ per $n ≥ 2$, per cui (e da qui in poi mi sono perso... )
$n^2 + (3/2)n + (1/2) ≤ n2 + n2 = 2 n^2$ per $n ≥ 2$,
Per cui $4 n^2$ (che sarebbe $c*g(n)$ ) e risulta $Ο (n^2)$


Potreste darmi una mano con quegli ultimi passaggi? Come fa a stabilire $c=4$?

grazie

[Eredir]

"Larios":Ma se avessi avuto solo $2n^2 + 3n + 1$ e mi venisse chiesto di trovarne l' O grande avrei qualche difficolta nella dimostrarazione:

si comincia nell' isolare $n^2$ ottnenedo $n^2 + (3/2)n + 1/2$

Si ha $(3/2)n + (1/2) ≤ n2$ per $n ≥ 2$, per cui (e da qui in poi mi sono perso... )
$n^2 + (3/2)n + (1/2) ≤ n2 + n2 = 2 n^2$ per $n ≥ 2$,
Per cui $4 n^2$ (che sarebbe $c*g(n)$ ) e risulta $Ο (n^2)$


Potreste darmi una mano con quegli ultimi passaggi? Come fa a stabilire $c=4$?

grazie

Hai verificato che $3/2n+1/2<=n^2$ per $n>=2$, quindi semplicemente si tratta di utilizzare questa maggiorazione per $n^2+3/2n+1/2$, ovvero $n^2+(3/2n+1/2)<=n^2+(n^2)=2n^2$ (ho messo le parentesi sperando che possano rendere più chiara la maggiorazione).
Ora è molto semplice, la tua espressione iniziale era $2n^2+3n+1$ quindi semplicemente si tratta di moltiplicare per due la disuguaglianza trovata prima e quindi $2n^2+3n+1<=4n^2$, dunque $c=4$.

[Larios1]

grazie per il chiarimento

[Larios1]

stavo provando a fare qualche esercizio supplementare e mi sono imbattuto in questo che mi ha lasciato un po perplesso

$7n^2 logn+ n logn$

riporto i vari passaggi per trovare O grande

$n^2 logn+ (n logn/7)$

$ (n logn/7) < n^2 logn$ per n > 1

riscrivo

$n^2 logn+ (n logn/7) < 2 * (n^2 logn)$

ottengo cosi in fine

$7n^2 logn+ (n logn) < 14n^2 logn$

Ma il risultato corretto $O(n^3)$ e infatti provando a dimostare con quest'ultimo viene verificato, dove sto sbagliando?

[Larios1]

up