Mathematics Asked by tyMind on February 9, 2021
In a book it is written that by writing f(n)=omega_infinity(g(n)) we mean that there exists a positive constant c such that f(n)>=cg(n)>=0 for infinitely many integers n. Whereas a Big Omega definition says that there exist positive constants c and n0 such that 0<=cg(n)<=f(n) for all n>=n0. My question is why is it not right to say that these definitions are equal when for the Big Omega definition there is a n>=n0 condition for n, which in my opinion tells that the definition must be true for infinitely many n’s that are just greater or equal to n0.
Suppose $f(n)=1$ and $g(n)=0$ when $n$ is even. Suppose $f(n)=0$ and $g(n)=1$ when $n$ is odd. With $c=1,$ the sets ${nin Bbb N: f(n)ge cg(n)ge 0}$ and ${nin Bbb N: g(n)ge cf(n)}$ are both infinite. But we do NOT have $f=O(g)$ nor $g=O(f).$
The Landau "big-$O$" notation is only concerned with the absolute values of the functions, and may be used when the variable $n$ can take non-integer values, and may be used when the variable approaches $rin Bbb R.,$
If it is understood that $n$ must be an integer then "$f(n)=O(g(n))$ as $nto infty$" means $$exists n'in Bbb N, exists c>0,forall nin Bbb N ,(n>n'implies |f(n)|le c|g(n)|,).$$
If the variable can take any real value, it is customary to use $x,$ not $n$. So "$f(x)=O(g(x))$ as $x toinfty$" means $$exists x'in Bbb R^+,exists c>0,forall xin Bbb R,(x>x'implies |f(x)|le c|g(x)|,).$$
If $rin Bbb R$ then "$f(x)=O(g(x))$ as $xto r$" means $$exists delta >0 , exists c>0 ,forall xin Bbb ,(0<|x-r|<delta implies |f(x)|le c|g(x)|,).$$ For example $(sin x)^2/x= O(x)$ as $xto 0.$ In some contexts $x$ may be restricted to values only $>r.$
Answered by DanielWainfleet on February 9, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP