0
$\begingroup$
  1. Geometric meaning of $O(1)$?
  2. Need $O(1)$ maps $0$ to $0$?

The definition of big O notation is clear for me.But such questions i could not understand. By definition $O(1)$ is any mapping which is bounded.For example $f(x)=O(1)$ as $x\to x_0$ means there is $M>0$ such that $|f(x)|\leq M$ whenever $x$ close to $x_0$

$\endgroup$
  • $\begingroup$ $O(1)$ denotes a bounded function, i.e. which stays under some horizontal line forever. You don't consider limits to a finite value such as $x_0$ but to infinity. $\endgroup$ – Yves Daoust Dec 7 '16 at 14:59
  • $\begingroup$ "Need $O(1)$ maps $0$ to $0$?": where do you get this strange idea from ? $\endgroup$ – Yves Daoust Dec 7 '16 at 15:01
  • $\begingroup$ You say "For example $f(x)=O(1)$ as $x\to x_0$ means there is $M>0$ such that $|f(x)|\leq M$ whenever $x$ close to $x_0$". Now let $x_0=0$ $\endgroup$ – Henry Dec 7 '16 at 15:03
  • $\begingroup$ So the answer is no of course right? O(1) need not map 0 to 0 $\endgroup$ – Jamal Gadirov Dec 7 '16 at 15:04
  • 1
    $\begingroup$ @Arthur It doesn't have to be all x, just those in the limit you consider. For example, $e^x $ is $O (1) $ near 0. $\endgroup$ – Ian Dec 7 '16 at 15:20
0
$\begingroup$

In big-o notation, when we say that a function $f$ is $O(x^2)$ we're basically saying that

$$|f(x)|\le M |x^2|$$ for some constant $M>0$ and for all $x>x_0$ for some $x_0$.

But $O$ is under-specified without a statement such as $x\to\infty$ or $x\to 0$.

For example: "$x^2=O(x)$ as $x\to 0$" is true; but "$x^2=O(x)$ as $x\to \infty$" is false.

In some areas, like computer science, people tend to consider this situation exclusively, so "$x\to\infty$", is understood without saying.

If we are talking about $x\to 0$, which is a different situation; we are considering $x$ near $0$, not large $x$.

  • $f(x) = O(x)$ as $x\to 0$ means: there is $C$ such that $|f(x)|\le C|x|$ for all $x$ sufficiently close to $0$. Such a function might look like this:

bowtie

That is, its graph is contained in some bowtie-shaped region like the one between the red lines.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.