Esercizio su limite inferiore
Potreste darmi qualche dritta su questo esercizio?
Si forniscano due funzioni $f(n)$ e $g(n)$ tali che $f(n) ∈ Ω(g(n))$ e $f(n) < g(n)$ per ogni $n ≥ 1$ .
E' per caso una domanda a tranello?
La conclusione a cui sono arrivato io è che non mi sembra possibile che entrambe le condizioni siano soddisfatte. Cioè se $f(n) ∈ Ω(g(n))$ significa che $f(n)$ sarà sempre $>= g(n)$ quindi com'è possibile soddisfare $f(n) < g(n)$ per ogni $n ≥ 1$?
Si forniscano due funzioni $f(n)$ e $g(n)$ tali che $f(n) ∈ Ω(g(n))$ e $f(n) < g(n)$ per ogni $n ≥ 1$ .
E' per caso una domanda a tranello?
La conclusione a cui sono arrivato io è che non mi sembra possibile che entrambe le condizioni siano soddisfatte. Cioè se $f(n) ∈ Ω(g(n))$ significa che $f(n)$ sarà sempre $>= g(n)$ quindi com'è possibile soddisfare $f(n) < g(n)$ per ogni $n ≥ 1$?
Risposte
Prima di tutto, giusto per capirci con la notazione, cosa rappresenta per te $ \Omega(g(n))$ ?
"Bossmer":
Prima di tutto, giusto per capirci con la notazione, cosa rappresenta per te $ \Omega(g(n))$ ?
Il limite inferiore di g(n). Come si rappresenta sennò?
Il mio libro la definisce cosi:
$f(n) ∈ Ω(g(n)) ⇔ ∃c > 0 ∃n 0 ∀n ≥ n 0 . c · g(n) ≤ f (n)$
Non mi ero accorto fossi nuovo del forum, quindi Benvenuto! 
Ma si rappresenta come ti pare, come tutte le cose l'importante è la definizione, la notazione e i nomi cambiano da libro a libro e a volta anche da capitolo a capitolo dello stesso libro.
Comunque, tornando all'esercizio, stando a quella definizione, se prendi $g(n)=2n$ e $f(n)=n$ è risolto, e la verifica è immediata, basta prendere $c=1/4$.
Ma si rappresenta come ti pare, come tutte le cose l'importante è la definizione, la notazione e i nomi cambiano da libro a libro e a volta anche da capitolo a capitolo dello stesso libro.
Comunque, tornando all'esercizio, stando a quella definizione, se prendi $g(n)=2n$ e $f(n)=n$ è risolto, e la verifica è immediata, basta prendere $c=1/4$.
Grazie mille!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo