[ALGORITMI] esercizio Notazione asintotica

[stefanaimon1]

Salve, qualcuno potrebbe spiegarmi come faccio a trovare la costante c e il valore di m in esercizi del tipo:
$ n = O(3n + 5) $
$ n^2 − 3n + 5 = O(n^2) $

anche utilizzando la definizione di O() non riesco a capire come risolvere gli esercizi...

[xneo1]

Allora, per prima cosa partiamo dalla definizione di O grande.

Una funzione f(n) è O(g(n)) se esistono due costanti c>0 e m>=0 tale che f(n) <= c * g(n) per ogni n>=m.

Adesso vediamo come risolvere gli esercizi.
C'è da precisare che quello che è importante in queste uguaglianze è che siano vere o false, la costante c e m servono solo per verificare la relazione.

Consideriamo la prima relazione:
n=O(3n+5)

quello che dobbiamo stabilire è se n<=c*(3n+5) per un certo n>m.

Osserviamo che se c=1 e m=0 abbiamo che n<=3n+5 già per n>=0.

Per il secondo esercizio prova tu, se non ci riesci lo risolviamo insieme.