Esercizi simboli di landau

Alecc90
Ciao a tutti ragazzi!

Devo fare il seguente esercizio:

Stabilire se l’affermazione è vera oppure falsa, dimostrandola nel primo caso ed esibendo un controesempio nel secondo.
$o(n)+O(n^2)=o(n)$

Dovrei usare le proprietà algebriche, giusto, ma in questo caso da quale parto?

io so che $f = o(g)$ implica $f = O(g)$
ma questo vuol dire che nel mio esercizio posso sostituire $o(n)$ con un $O(n)$?

Grazie a tutti!

Risposte
Giuly191
"Alecc90":

io so che $f = o(g)$ implica $f = O(g)$
ma questo vuol dire che nel mio esercizio posso sostituire $o(n)$ con un $O(n)$?

Volendo puoi farlo, ma secondo me è più facile se applichi direttamente le due definizioni di $o$ e $O$.

Alecc90
Perchè se sostituisco $o(n)$ con $O(n)$ otterrei: $O(n)+O(n^2)$ e una proprietà dice che:

$O(f) + O(g) = O(max{ | f | , | g | })$

e, quindi mi rimarrebbe: $O(n^2)=o(n)$

e a me, a questo punto, verrebbe da dire FALSO, no?

Tu, come procederesti, sostituendo direttamente le definizioni..?

Giuly191
L'uguaglianza è falsa, quindi il risultato a cui arrivi è corretto.
Però potresti essere un filo più rigoroso usando le definizioni, come ti dicevo prima.
Per $n-> +oo$ si ha: $o(n)+O(n^2)n^2/n^2=o(n)+Cn^2$.
A questo punto dovresti provare o smentire che $o(n)+Cn^2=o(n)$, puoi fare così (sempre quando $n->+oo$):
$(o(n)+Cn^2)/n = (o(n))/n + Cn$, il primo termine è infinitesimo per definizione, mentre il secondo tende banalmente a $+oo$.
Quindi l'uguaglianza iniziale è falsa.

Alecc90
"Giuly19":

Per $n-> +oo$ si ha: $o(n)+O(n^2)n^2/n^2=o(n)+Cn^2$.
A questo punto dovresti provare o smentire che $o(n)+Cn^2=o(n)$, puoi fare così (sempre quando $n->+oo$):
$(o(n)+Cn^2)/n = (o(n))/n + Cn$, il primo termine è infinitesimo per definizione, mentre il secondo tende banalmente a $+oo$.
Quindi l'uguaglianza iniziale è falsa.


mmh..io so che $f(x)=O(g(x))$ se $exists M>0: |f(x)|≤M |g(x)|$

ma, in questo caso...scusa...ma mi sto perdendo un attimo... :lol:
Allora hai moltiplicato $n^2/n^2$ che tanto è uguale a $1$ a $O(n^2)$, ma perché?

Scusa..mi sono letteramlente perso... :cry:

Giuly191
Perchè se $f(x)=O(g(x))$ per $x-> a$ allora $limSup _(x ->a) |f(x)|/|g(x)| = M in RR$.
Comunque anche il tuo ragionamento mi pare andasse bene, solo cerca di concluderlo!

Alecc90
Ok, perfetto, hai ragione, ma, quindi, l' $M$, nell'esempio che mi hai proposto sarebbe $n^2$

Comunque ok, al massimo seguo il mio ragionamento!! :)
Ma, non va bene se quando arrivo ad avere $O(n^2)=o(n)$ dico semplicemente che l'uguaglianza è falsa?
grazieeee!

Giuly191
No $M in RR$, $n$ non sta in $RR$ quando lo mandi a $+oo$..
Comunque certo che va bene, ma devi dimostrarlo! :)
Non è per niente difficile, ti basta prendere una successione $a_n=O(n^2)$ e far vedere che non è $o(n)$.
Oppure direttamente prendere $(O(n^2))/n$ e far vedere che non tende a $0$ quando $n->+oo$.

Alecc90
"Giuly19":


Non è per niente difficile, ti basta prendere una successione $a_n=O(n^2)$ e far vedere che non è $o(n)$.
Oppure direttamente prendere $(O(n^2))/n$ e far vedere che non tende a $0$ quando $n->+oo$.


Quindi, ad esempio potrei prendere il mio $a_n=n$
e dire che $a_n=O(n^2)$ se $exists C>0 : a_n <= C|n^2|$
Prenderei tipo $C=3$ e avrei che $n<=3|n^2|$
ed è vero $=>a_n=O(n^2)$

Poi sempre con $a_n=n$
direi che $a_n=o(n)$ se $lim_(n->oo) (n/n)=0$ ma in questo caso tale limite è uguale a $= 1$
e quindi $a_n$ non è un $o(n)$

E' giusto dimostrato così?

Grazie mille!!!!! :):):)

Giuly191
Perfetto!

Alecc90
Ehi Giuly19, (o chiunque altro :) ) se mi puoi aiutare avrei un dubbio su un altro esercizio di questa tipologia:

Nell’ipotesi che per per $n->+oo$ si abbia $a_n = n^2 + o(n)$ e $b_n = −n^2 + n + O(n)$, stabilire se le seguenti
affermazioni sono vere oppure false:
a) $a_n =Θ(n^2)$
b) $(a_n + b_n)$ ~ $n$

Allora:
Io so che $f(n) = Θ(g(n))$ se
$exists C_1,C_2 >0 :$ $C_1*|g(n)|<=f(n)<=C_2*|g(n)|$

a) A me verrebbe da dire falso, però avevo un dubbio: in questo caso di $a_n$ possiamo trascurare l' $o(n)$ ?

b) Sostituiamo e ci rimane: $o(n)+n+O(n)$
per il ragionamento precedente avrei $n+O(n)+O(n) = n+O(n)$
Ma ora mi sono bloccato perché, anche in questo caso non so se posso trascurare l'$O(n)$
e dire se $n$~ $n$, che sarebbe vero...

Grazie ancora per l'aiuto! :)

Giuly191
Per l'affermazione a) sei fuori strada, quasi per definizione puoi dire che $a_n sim a_n + o(a_n)$, e se non sbaglio $sim =>$ "dello stesso ordine". ($a_n/b_n -> 1$ quando $n->+oo$, $=>$ $1/2 b_n <= a_n <= 3/2 b_n$ definitivamente).
In pratica la risposta è puoi trascurare l'$o(n)$, ma devi dimostrarlo, non è difficile, provaci (fai prima dimostrando quello che ti ho suggerito sopra).
Per la b) la questione è se è vero che $n+O(n) sim n$; per questa ti basta un controesempio, perchè è falsa.

Alecc90
Mmh..non ho capito tutto chiaramente ma ho provato a ragionarci su..

Allora tu mi hai detto:
"Giuly19":
Per l'affermazione a) sei fuori strada, quasi per definizione puoi dire che $a_n sim a_n + o(a_n)$, e se non sbaglio $sim =>$ "dello stesso ordine". ($a_n/b_n -> 1$ quando $n->+oo$, $=>$ $1/2 b_n <= a_n <= 3/2 b_n$ definitivamente).
In pratica la risposta è puoi trascurare l'$o(n)$, ma devi dimostrarlo, non è difficile, provaci (fai prima dimostrando quello che ti ho suggerito sopra).


Allora sisi se $a_n sim b_n$ vuol dire che $a_n$ e $b_n$ sono dello stesso ordine... E, quindi, come mi hai detto tu avrei che il limite di $a_n/b_n -> 1$ quando $n->+oo$...

Solo che non ho proprio capito come fare per poter dimostrare, sulla base di queste cose, che l'$o(n)$ è trascurabile :? :?

"Giuly19":
Per la b) la questione è se è vero che $n+O(n) sim n$; per questa ti basta un controesempio, perchè è falsa.


E quindi il problema mi si trascina anche dopo, ma penso che a questo punto mi sfugga proprio qualcosa, perché questo vuol dire che, in questo caso l'$O(n)$ non può essere trascurato, come facciamo per l'$o(n)$, giusto?

grazie mille e scusa ma davvero non so più da che parte girarmi.... :cry: :cry:

Giuly191
Ma dai per la a) è semplice! Devi dimostrare che $(a_n + o(n))/a_n=1+(o(a_n))/a_n -> 1$ quando $n->+oo$. Praticamente ti basta applicare la definizione. Nel caso degli O-grandi invece non è più sempre vero che $1+(O(a_n))/a_n -> 1$. Non è difficile nemmeno questo, ti ho dato lo spunto giusto?

Alecc90
"Giuly19":
Ma dai per la a) è semplice! Devi dimostrare che $(a_n + o(n))/a_n=1+(o(a_n))/a_n -> 1$ quando $n->+oo$. Praticamente ti basta applicare la definizione. Nel caso degli O-grandi invece non è più sempre vero che $1+(O(a_n))/a_n -> 1$. Non è difficile nemmeno questo, ti ho dato lo spunto giusto?


Mmh..ma perchè quella cosa è vera per gli o-piccoli, ma non sempre per gli O-grandi?

E poi...... :oops: ...sinceramente non ho molto capito perché $1+(o(a_n))/a_n -> 1$ quando $n->+oo$.... :( :( :cry:

Giuly191
Per questa volta te lo risolvo io, però la prossima tieni bene a mente le definizioni e cerca di applicarle!
Cos'è un o piccolo di $a_n$? Qualcosa che fa così: $lim_(n->+oo) (o(a_n))/a_n = 0$.
Quindi è chiaro che $lim_(n->+oo) 1 + (o(a_n))/a_n =1$.
Per quanto riguarda gli O grandi ti basta un esempio stupido: $2n=O(n)$ infatti $2n<=Cn$, ($c=2$), e il limite diventa:
$lim_(n->+oo) 1 + (O(a_n))/a_n =lim_(n->+oo) 1 + 2n/n =3$.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.