3
$\begingroup$

I came across such a function written by $O$. Can you please tell me what is this? Actually I see this function during proofs or error finding. I am familiar with big-O notation in algorithmic complexity, but I am talking about when it is used in math. Example:

enter image description here

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

It's used in the exact same way as in complexity theory

$f=O(g)$ if and only if there exists a $k$ and an $N$ such that for all $x>N$, $f(x)<kg(x)$

It's not a new symbol. It's generally used in a manner similar to in complexity theory: to lump together the terms into a single term that dominates them in the analysis.

The main difference in the usage is that in error analysis, it's the slowly growing functions that matter rather than the fast growing ones. When $x$ is small, $x>x^2>x^3>\ldots$. It's usually used in the context of taylor series, which allows you to secure small values of $x-c$ (by centering the series near $x$). Therefore the dominating term is the smallest exponent, in contrast to evaluation at large values (such as in CS run-time) where the dominating term is the large exponent.

There is a discussion of this here

$\endgroup$
2
  • 1
    $\begingroup$ My thoughts now are like that: "so what?" :) Can you explain why people use it? Always reading some proof or something, I am like "hmm, okay, then okay" and suddenly here is this $O$ function! Usually adding this at the end of the formula, so that: $f_1(x) + ... bla-bla + ... O(x^3)$ for example. What is this? Why do people need this? $\endgroup$
    – Turkhan Badalov
    Mar 22, 2017 at 20:21
  • $\begingroup$ @TurkhanBadalov I'm not sure what you're looking for besides "it's a concise way to express the idea that the remaining terms are dominated by a term of degree three." It's useful for doing algebra with inequalities because it lets you ignore higher degree terms. $\endgroup$
    – Stella Biderman
    Mar 22, 2017 at 20:25
1
$\begingroup$

It is the same big-O as in algorithmic complexity. The purpose in the specific context being to simplify the formal handling of terms that vanish in the asymptotic limit.

http://www.cs.cornell.edu/courses/cs312/2004fa/lectures/lecture16.htm https://en.wikipedia.org/wiki/Asymptotic_analysis

$\endgroup$
4
  • $\begingroup$ Why do people use it? To not calculate all terms with coefficients? And instead they replace all them with the complexity function? $\endgroup$
    – Turkhan Badalov
    Mar 25, 2017 at 19:59
  • $\begingroup$ @TurkhanBadalov Yup, more or less. It's also a way to ignore all of the terms that don't matter (as error analysis usually hinges upon the coefficient of the lowest degree term) $\endgroup$
    – Stella Biderman
    Mar 25, 2017 at 22:12
  • $\begingroup$ @StellaBiderman, of the lowest degree or the highest? Where can I read about this? $\endgroup$
    – Turkhan Badalov
    Mar 25, 2017 at 22:17
  • $\begingroup$ @TurkhanBadalov I've edited my earlier answer to include more info and answer that question $\endgroup$
    – Stella Biderman
    Mar 25, 2017 at 22:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .