0
  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$

Jamal Gadirov
  • 205
  • $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. –  Dec 07 '16 at 14:59
  • "Need $O(1)$ maps $0$ to $0$?": where do you get this strange idea from ? –  Dec 07 '16 at 15:01
  • 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$ – Henry Dec 07 '16 at 15:03
  • So the answer is no of course right? O(1) need not map 0 to 0 – Jamal Gadirov Dec 07 '16 at 15:04
  • No, it doesn't need to map $0$ to $0$. What $f(x)=O(1)$ means is, by definition, that there is some real number $c$ such that $|f(x)|\leq c$ for all $x$. – Arthur Dec 07 '16 at 15:15
  • 1
    @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. – Ian Dec 07 '16 at 15:20

1 Answers1

0

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.