Esercizio - Definizione O grande
Definizione.
Una funzione $ g(n) ∈ O(f(n)) $ se esiste una costante $ c!=0 $ ed un valore $ n_0 > 0 $ per cui $ g(n)≤c f(n) $ per ogni $ n>n_0 $.
Esercizio.
Dimostrare, o confutare la seguente espressione:
se $ f(n) ∈ O(h(n)) $ e $ g(n) ∈ O(h(n)) $ allora $ f(n) ∈ O(g(n)) $
La mia soluzione:
Prendendo per esempio le seguenti funzioni possiamo confutare facilmente l'espressione sopracitata:
$ f(n) = n^5, g(n) = n^4, h(n) = n^6 $
Credo che si possa scrivere meglio così:
$ f(n) = n^5, g(n) = n^4, h(n) = n^5 $
Il mio dubbio:
Per confutare questa espressione, basta questo controesempio?
Ci sono modi migliori, o più approfonditi per risolvere questo esercizio?
Edit: ho sostituito la parola "definizione" con "espressione".
Una funzione $ g(n) ∈ O(f(n)) $ se esiste una costante $ c!=0 $ ed un valore $ n_0 > 0 $ per cui $ g(n)≤c f(n) $ per ogni $ n>n_0 $.
Esercizio.
Dimostrare, o confutare la seguente espressione:
se $ f(n) ∈ O(h(n)) $ e $ g(n) ∈ O(h(n)) $ allora $ f(n) ∈ O(g(n)) $
La mia soluzione:
Prendendo per esempio le seguenti funzioni possiamo confutare facilmente l'espressione sopracitata:
$ f(n) = n^5, g(n) = n^4, h(n) = n^6 $
Credo che si possa scrivere meglio così:
$ f(n) = n^5, g(n) = n^4, h(n) = n^5 $
Il mio dubbio:
Per confutare questa espressione, basta questo controesempio?
Ci sono modi migliori, o più approfonditi per risolvere questo esercizio?
Edit: ho sostituito la parola "definizione" con "espressione".
Risposte
Una definizione non si confuta.
bravo grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo