O grande

[ferra031]

Ciao a tutti, mi serve il vostro aiuto, potreste dirmi quali calcoli devo effettuare per verificare che: $5n^2 + n = O(n^2)$ ?

[_luca.barletta]

Devi usare la definizione di O grande.

[ferra031]

La definizione la so: $f(n)$ è "O grande" di $g(n)$ -> $f(n) = O(g(n))$, se esistono $c > 0$, $n0 \in N$ tali che per ogni $n > n0$ sia $f(n) <= c * g(n)$. Il problema è che sulle dispense sulle quali studio c'è scritto che $5n^2 + n = O(n^2)$ è vero. Però se pongo $c = 4$ e $n0 = 10$ sostituendo trovo che $f(n) = 510$ e $g(n) = 400$, in questo modo chiaramente non è verificato $f(n) <= c * g(n)$. Quindi chiaramente sto sbagliando ed è per questo che vorrei sapere l'essatto procedimento per determinare se una generica funzione $f(n)$ sia $O(g(n))$.

[gugo82]

E se poni [tex]$c=10000$[/tex]?

Ad ogni modo, la disuguaglianza [tex]$|f(n)|\leq c\ |g(n)|$[/tex] la devi verificare definitivamente, ossia a partire da [tex]$n_0$[/tex] in poi.
Se riguardi la definizione e supponi (come accade in questo caso) che [tex]$g(n)\neq 0$[/tex] per [tex]$n$[/tex] abbastanza grande, puoi sicuramente scrivere:

[tex]$\left| \frac{f(n)}{g(n)}\right| \leq c$[/tex],

la quale significa che la successione [tex]$\tfrac{f(n)}{g(n)}$[/tex] (definita per [tex]$n$[/tex] sufficientemente grande) è limitata.
In particolare ciò si verifica quando la successione [tex]$\tfrac{f(n)}{g(n)}$[/tex] è convergente (noto risultato di Analisi I), quindi puoi affermare che vale l'implicazione:

[tex]$\text{$\lim_n \frac{f(n)}{g(n)}$ esiste finito}\ \Rightarrow\ f(n)=\text{O}(g(n))$[/tex].

Nel caso in esame la condizione [tex]$\text{$\lim_n \frac{f(n)}{g(n)}$ esiste finito}$[/tex] è abbondantemente verificata, quindi...