Regole O grande
utilizzando le regolate degli O grande devo dimostrare che :
$7n^2+5n+4$ è $O(n^2)$
Quindi ho pensato che:
punto1: per $n>1$ da cui $\text $ $5n+4 <= 7n^2$
pertanto $5n+4$ è $O(7n^2)$
punto2:
mentre la regola dei fattori costanti è $O(7n^2)= O(n^2)$
Secondo voi va bene ?
Al punto 1 non ci sono regole da applicare ma devo
soltanto trovare dei valori per cui valga $f(n)<=cg(n)$
E' possibile al punto 1 in qualche modo applicare la regola della somma ? Cioè se $f(n) è O(g(n))$ allora $f(n)+g(n)=O(g(n))$
$7n^2+5n+4$ è $O(n^2)$
Quindi ho pensato che:
punto1: per $n>1$ da cui $\text $ $5n+4 <= 7n^2$
pertanto $5n+4$ è $O(7n^2)$
punto2:
mentre la regola dei fattori costanti è $O(7n^2)= O(n^2)$
Secondo voi va bene ?
Al punto 1 non ci sono regole da applicare ma devo
soltanto trovare dei valori per cui valga $f(n)<=cg(n)$
E' possibile al punto 1 in qualche modo applicare la regola della somma ? Cioè se $f(n) è O(g(n))$ allora $f(n)+g(n)=O(g(n))$
Risposte
Ti dirò, puoi usare direttamente la definizione.
Dovresti determinare una costante $C >0$ tale che $7n^2 + 5n +6 <= C n^2$ e ciò equivale a determinare $C$ in modo che $7 + 5/n + 6/n^2 <= C$.
Visto che $5/n$ e $6/n^2$ sono strettamente decrescenti, per soddisfare la precedente basta prendere $C=18$.
Dovresti determinare una costante $C >0$ tale che $7n^2 + 5n +6 <= C n^2$ e ciò equivale a determinare $C$ in modo che $7 + 5/n + 6/n^2 <= C$.
Visto che $5/n$ e $6/n^2$ sono strettamente decrescenti, per soddisfare la precedente basta prendere $C=18$.
"gugo82":
Ti dirò, puoi usare direttamente la definizione.
Hai ragione ma mi sono dimenticato di scrivere che l'esercizio richiedeva esplicitamente di dimostrare la funzione utilizzando le regole di semplificazione delle espressioni O-grande. Alla luce di ciò può andar bene la mia deduzione o forse devo applicare qualche altra regola al punto 1 ?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo