3
$\begingroup$

I understand big O notation in computational complexity theory, but I don't see how it applies in the equation below.

From Pattern Recognition and Machine Learning:

If we weren't familiar with the rules of ordinary calculus, we could evaluate a conventional derivative $dy/dx$ by making a small change to the variable $x$ and then expanding in powers of $\epsilon$ , so that $y(x + \epsilon) = y(x) + \frac {dx}{dy}\epsilon + O(\epsilon^2)$

and finally taking the limit $\lim\epsilon\to 0$.

$\endgroup$
3
$\begingroup$

It means exactly the same thing. It means there is a constant $c$ such that the term is $\le c \cdot \epsilon^2$ (where $c$ does not depend on $\epsilon$). Big-O notation is not unique to computer science; it is also widely used in mathematics. See https://en.wikipedia.org/wiki/Big_O_notation, which explains some ways it is used in mathematics.

$\endgroup$
  • 4
    $\begingroup$ There are two differences: (1) this O bounds the magnitude (absolute value) of the error term, (2) the limit is $\epsilon\to0$ rather than $n\to\infty$; so it might hold only for $\epsilon < \epsilon_0$ for some small $\epsilon_0 > 0$. $\endgroup$ – Yuval Filmus Feb 16 '15 at 3:02

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.