Esercizi simboli di landau
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!
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
"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$.
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..?
$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..?
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.
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.
"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...
Allora hai moltiplicato $n^2/n^2$ che tanto è uguale a $1$ a $O(n^2)$, ma perché?
Scusa..mi sono letteramlente perso...
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!
Comunque anche il tuo ragionamento mi pare andasse bene, solo cerca di concluderlo!
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!
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!
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$.
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$.
"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!!!!!
:):)
Perfetto!
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!
) 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!
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.
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.
Mmh..non ho capito tutto chiaramente ma ho provato a ragionarci su..
Allora tu mi hai detto:
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
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....
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....
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?
"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......
...sinceramente non ho molto capito perché $1+(o(a_n))/a_n -> 1$ quando $n->+oo$.... 
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$.
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$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo