esercizio di Algoritmi e strutture dati [vi supplico aiutatemi]

[*MATRIX*]

raga mi siete rimasti solo voi

Usando esplicitamente la definizione di O-grande dimostrare la verità o la falsità di:

esercizio 1 (3/5)n^2-3n+2=O(n^2)

esercizio 2 4log n^(3/2)+7logn=O(logn)

mi potreste spiegare passo passo come si svolgono?

vi prego

[PGI-Bis]

Stante la definizione della notazione O-Grande (f(n) è O(g(n)) se esistono due valori positivi c ed N tali che f(n) <= cg(n) per ogni n maggiore o uguale a N), devi trovare almeno una coppia di valori c ed N che verifichi la disequazione:

(3/5)n^2-3n+2 <= c(n^2), per ogni n maggiore di N

Se questa coppia esiste, allora (3/5)n^2-3n+2 è O-Grande di n^2 . Idem per la seconda.

Come determinare l'esistenza di questa coppia è cosa che lascio più che volentieri a chi si intenda di analisi .

[*MATRIX*]

Originariamente inviato da PGI-Bis

Come determinare l'esistenza di questa coppia è cosa che lascio più che volentieri a chi si intenda di analisi .

grazie per le risposte ma cmq non riesco a capire come arrivare ai due numeri c ed n

il libro fa un unico esempio e da direttamente le soluzioni a non spiega il procedimento passo passo io di quello ho bisogno

mi basta anche solo il primo esercizio

help

[Ziosilvio]

Originariamente inviato da *MATRIX*

Usando esplicitamente la definizione di O-grande

Ossia: date due funzioni f,g : IN --> IN, si dice che f(n) è O-grande di g(n), e si scrive f(n) = O(g(n)), se esistono C>0 ed n0 in IN tali che f(n) <= C*g(n) per ogni n>=n0.
In altre parole: f(n) è O(g(n)) se, a partire da un certo punto in poi, è maggiorata da un opportuno multiplo di g(n).
Recuperando le nozioni di Analisi che sicuramente hai, fai presto a vedere che:
- n^r = O(n^s) se e solo se n<=s;
- log n = O(n^r) per ogni r, e n^r = O(a^n) per ogni r>=0 e a>1;
- se f(n) = O(g(n)), allora (f(n))^r = O((g(n))^r) per ogni r>=0.

esercizio 1 (3/5)n^2-3n+2=O(n^2)

Prova a porre C = 1, n0 = 1.

esercizio 2 4log n^(3/2)+7logn=O(logn)

Prova a porre k = log n, e vedi cosa esce fuori...