1

I am a computer science student and I am familiar with big-oh notation in algorithm analysis books. But the book I am working for mathematical analysis is using somewhat different asymptotics definitions to analyze vanishing rate of the error term of the Taylor series. Here is the definition:

Defn: We say $f(t)$ vanishes at least to order p (at the origin), and write $f(t) = O(p)$, if there are positive constants $\delta$ and $C$ for which

$$\mid f(t) \mid \leq C \mid t \mid^p$$ when $\mid t \mid \lt p$.

I don't understand this "vanishes at least to order p" part. Later, the book says; if $f(t)$ vanishes to at least to order p, there is no reason to think $f(t)$ vanishes to higher order than p.

If it can not vanish to order higher than p, doesn't that mean it vanishes at most to order p, not at least? Can you clarify this definition and explain the last bold-faced part? Can a function $f(t) = O(p)$ vanish to order greater than p?

meguli
  • 640
  • 1
    "there is no reason to think that it vanishes to higher order than $p$" but it still could. This is just saying that there are examples of $f$ for both scenarios. There are some $f$ which are $f(t)=O(p)$ which do not vanish to any higher orders than $p$, and there are other $f$ which are also $f(t)=O(p)$ which do vanish to at least one higher order than $p$. – JMoravitz Aug 15 '17 at 22:47
  • if we wanted to explore how a polynomial grows as the variable(s) grow(s) we can relate it to the highest degree example: $$x^3+2x^2+8x+1$$ we can show that after certain values of x the lower exponents don't really add much compared to the $x^3$. for x> 0, 8x>1 for x>4 , $2x^2 >8x$ for x>2 $x^3>2x^2$ so by x=5 the greatest change of the value comes from that $x^3$ term. –  Aug 15 '17 at 22:51
  • I think the given definition of big-oh in the book and above is not related to growth rates I know from algorithms but related to vanishing rates. – meguli Aug 15 '17 at 22:53

1 Answers1

2

If $|f(t)|\leq C|t|^p$, it might also be the case that $|f(t)|\leq D|t|^{p+1}$, because $|t|^{p+1}\leq |t|^p$ near $t=0$. But it must be the case that $|f(t)|\leq C|t|^k$ for $k<p$ because then $|t|^p\leq |t|^k$ near $t=0$. The statement "$f(t)$ is $O(p)$" does not say $p$ is the sharpest bound you can get, but it does imply a minimal degree of sharpness. As a result, it is best to read the statement as guaranteeing a minimal degree of vanishing, not specifying the best possible bound. That is why your book tells you to call this property vanishing to "at least" order $p$: they don't want you to make the mistake of thinking the order is exactly $p$.

Just look at a concrete example. Say you know $|f|$ is bounded by a constant times $t^2$. This means $|f|$ is also bounded by a constant times $|t|$, because $t^2<|t|$ for small nonzero $t$. But you don't know whether you can do better and bound $|f|$ by a higher-order power.

The general point is that if $a<b$ and you are interested in some $c<b$, it might be true that $a<c$, but it certainly doesn't have to be true.

symplectomorphic
  • 18,604
  • So it is sure to vanish to order p and less, and it might vanish to order greater than p. – meguli Aug 15 '17 at 23:03
  • @meguli precisely. – Simply Beautiful Art Aug 15 '17 at 23:11
  • @meguli: yes, that's right. – symplectomorphic Aug 15 '17 at 23:16
  • I think the trouble is that you were reading "there is no reason to think it vanishes to higher order" as "there is reason to think it doesn't vanish to higher order." That is a scope error. The book meant is that if all you know is that a function is $O(p)$, that, in itself, is not a reason for thinking it vanishes to higher order. But you might, by some deeper analysis, find an independent reason to conclude it does in fact vanish to higher order. – symplectomorphic Aug 15 '17 at 23:22