3

$f(x) = O(g(x))$ means that $\frac{f(x)}{g(x)}$ is bounded. But $x=O(x^2 + 1),\ x\in \mathbb R$ while $x\ne O(x^2)$. Is there a human friendly explanation of what $O$ is? the definitions I saw are as follows:

  1. f, g: E → R, a is a limit point of E. If there are $\dot{U}_a$ and a function ϕ: E → R, f(x)=ϕ(x)⋅g(x) and ϕ(x) is bounded in $\dot{U}_a$∩E , then f = O(g)
  2. f, g: E→R. ∃ C>$0$: |f(x)| ≤ C ⋅ |g(x)| ⇒ f=O(g) in E and examples:

sin x = O(x) $x \in R$

cos x ≠ O(x) $x \in R$

x ≠ O(sin x) $x \in R$

x = O($x^2+1$) $x \in R$

x ≠O($x^2$) $x \in R$

  • 5
    you need to specify behaviour of $x$. I mean $x\to 0$ or $x\to \infty$? – RFZ Apr 28 '22 at 17:23
  • 1
    @PlayGame, $x \in R$ i guess it's legit for both cases – user1063088 Apr 28 '22 at 17:27
  • $x=O(x^2)$ as $x\to +\infty$, but $x\neq O(x^2)$ as $x\to 0$. I mean $x<x^2$ for $x>1$, so the first case is clear. For the second, note that $x/x^2 =1/x$ is not bounded as $x\to 0$. You can say that $x=O(x^2+1)$ for all real $x$ since $x<x^2+1$ for all real $x$. – Gary Apr 29 '22 at 00:31
  • Big-O is used very differently in different applications. Usually either looking only at $x\to\infty$ and not concerned about $x\to0,$ or looking only at $x\to0$ and not concerned about $x\to\infty.$ I don't think I've ever seen someone define big-O so that $f(x)\leq c\cdot g(x)$ for every real $x.$ I suggest you edit your question so it starts with the precise definition of big-O exactly as it was shown to you, word for word and symbol for symbol. We can't explain what we've never seen. – David K Apr 29 '22 at 00:57
  • @DavidK, there is a test in a course where I'm supposed to answer whether a function is O of another function for every real x. I guess it's only possible if f(x) = O(g(x)) for both $x \to 0$ and $x \to \infty$ but i lack the grasp on the concept itself to solve it – user1063088 Apr 29 '22 at 03:26
  • 1
    The first definition seems to be missing some information about $\dot U_a.$ Put the definition(s) in the question, that way (1) people will see them, (2) they're easier to format and to read, (3) you can edit them to fix mistakes. Anyway, neither of those definitions necessarily takes all of $\mathbb R$ as the domain of $f$ or $g.$ But I suppose it is a legitimate question to ask, "What if $E=\mathbb R$?" That would provide a lot of valuable "context" for your question. – David K Apr 29 '22 at 13:36

2 Answers2

2

The general definition of big-$O$ that I've seen is that $f(x)\in O(g(x))$ if there exist constants $c>0$ and $n_0>0$ such that $$f(x)\leq c\cdot g(x)$$ for all $x\geq n_0$. That is to say, $f(x)\in O(g(x))$ if $g$ is "eventually bigger" than $f$, modulo some constant multiple.

1

The given definitions are more abstract than the usual definitions, which I think makes this question difficult to approach from a "human friendly" perspective (since the intuitions most people have about big-$O$ are oriented toward the usual definitions).

There are two typical uses of big-$O$ that I am aware of. One concerns asymptotic behavior of a function as the input to the function tends toward $+\infty.$ The other concerns the behavior of a function as the input tends toward zero.

A typical application of the "tends toward $+\infty$" is when talking about the running time of a computer algorithm. Then we might say that $f(n) = O(g(n))$ if there is a finite constant $M$ such that $$ \lvert f(n)\rvert \leq M \lvert g(n) \rvert$$ whenever $n$ is greater than some constant $n_0.$

If you have a program that takes a list of $n$ numbers and takes $1000 + 10n + 2n \ln(n)$ milliseconds to return the list sorted in increasing order, we might say the algorithm's running time is $n \ln(n)$. Clearly, for $n=1$ there is no constant $M$ that can make the equation $ \lvert f(n)\rvert \leq M \lvert g(n) \rvert$ true for this algorithm (where $f(n)$ is the actual running time and $g(n) = n\ln(n)$), but that is OK, because for large $n$ the inequality is easy to satisfy, and for this kind of analysis we are only worried about what happens for large values of $n.$ (It is assumed that algorithms that work OK for large $n$ finish even faster for small $n$.)

Another typical application is where $u(x)$ is some easier-to-compute approximation of a function $v(x)$ near a particular value of $x$, usually $x=0.$ For example, $u(x) = x$ is an approximation of the function $\sin(x)$ near $x=0.$ The error of this approximation, $x - \sin(x),$ is $O(x^3)$. An implication of this $O(x^3)$ statement is that if we are not happy with the kinds of errors we get when we use this approximation for $x$ in the interval $-0.1 < x < 0.1,$ we can still apply the approximation on the smaller interval $-0.01 < x < 0.01,$ and although we have only reduced the size of the interval by a factor of $10,$ the size of the error is reduced by roughly a factor of $1000.$

But an even better approximation is $u(x) = x - \frac16 x^3.$ Now the error is $x - \frac16 x^3 - \sin(x),$ which is $O(x^5)$, meaning that if we don't like the errors we get when $-0.1 < x < 0.1,$ the errors for $-0.01 < x < 0.01$ will be roughly a factor of $100,000$ times smaller.

Obviously we get very different big-$O$ conclusions when the limit point is $+\infty$ than we do when the limit point is $0.$ We can distinguish the two cases by including the limit point explicitly in the notation:

$$ 1000 + 10n + 2n \ln(n) = O(n\ln(n)),\quad n \to \infty,$$

$$x - \frac16 x^3 - \sin(x) = O(x^5),\quad x \to 0. $$


If $\dot U_a$ in the first definition denotes a neighborhood of the limit point $a,$ then the first definition is a generalization of at least the case where the function's input tends toward zero. If the domain of the function is unbounded above and if we interpret the set $\{x \mid x > x_0\}$, where $x_0$ is a constant, as a neighborhood of $+\infty,$ then this definition also covers the "tends toward $+\infty$" case.

In my explanation of the "tends toward $+\infty$" case I used a constant $M$ rather than the function $\phi,$ but that is easily reconciled by setting $M$ to an upper bound of $\lvert\phi(x)\rvert$ on the relevant neighborhood of the limit point $a.$ Then if it is true that for any $x$ in that neighborhood of $a,$ $$ f(x) = \phi(x) g(x),$$ it is also true that $$ \lvert f(x)\rvert \leq M \lvert g(x) \rvert.$$ If what we start with is $\lvert f(x)\rvert \leq M \lvert g(x) \rvert$ then we just need to set $\phi(x)$ to $M$ or $-M$ at each point in order to satisfy the definition that uses $\phi.$

By the way, if we make sure that $g(x)$ is a positive function then we can omit the absolute value around $g(x).$

The second definition is a little more restrictive. If we had the freedom to choose $E$ after knowing what functions we wanted to compare, we could just reduce $E$ to some suitable neighborhood of a limit point that we were interested in, and it would work much the same as the first definition. But it seems we are to be given the domain $E$ up front and must live with whatever is given. This will make a lot of big-$O$ calculations fail that would otherwise have been useful in analysis of algorithmic running time or that would have been useful in analysis of approximations of functions, just because we start with an unsuitable domain $E$ for the particular analysis we want to do.

The wording of the examples for this definition is also puzzling. What does it mean that $x \in R$? Since this particular definition includes the qualifier "in $E$" as part of its big-$O$ notation, a much clearer expression of the first two examples would have been,

$$ \sin x = O(x) \ \text{in $R$}, $$

$$ \cos x \neq O(x) \ \text{in $R$}. $$


It's still not clear what kind of "human friendly" meaning you're supposed to extract from these examples, especially examples like the $\cos x$ example. My best guess (not having the full context of the course materials you're using) is that the purpose of this exercise is to push you beyond the boundaries of "human friendly" thinking into thinking about how the symbols and logic of mathematics work in a more rigorous manner. Unfortunately, unless there is something missing in your transcription of the definitions and examples, if the purpose of this exercise is as I guessed then it has missed the mark, since the notations don't actually work in a rigorous manner: you have notations that apparently mean something but what they mean has not been defined.

David K
  • 98,388
  • i don't get the examples. not sure where the approximations come from. i guess you are right there is no trick or secret, you just either get it or not. thank you – user1063088 May 07 '22 at 16:11