0
$\begingroup$

Big-O notation is used to show the relative growth rates of functions. For example, $2x^2+3x=O(x^2)$ or $4x^2-2x+5=O(x^2)$, implying for $x\to\infty$, the limit of their ratio is a non-zero constant.

On this post and Wikipedia page, it was stated several issues with the use of the symbol $=$.

Can the symbol of equivalence $\equiv$ used instead to resolve the issues. Then it can be written: $2x^2+3x\equiv 4x^2-2x+5\equiv O(x^2)$ just like in modular arithmetic. It would imply something like the first function is congruent to the second function mod $C$. Consequently it would be transitive.

Yes, there can be an inconsistency with the fact that $O(f(x))$ represents a class of functions. Belonging of a function to a class of functions is represented with $\in$ just like in $f(x)\in C^2$ (the class of twice differentiable functions). Does it make sense or is it a serious violation of the math notations?

$\endgroup$
  • $\begingroup$ It is an acceptable notation, but non-standard. Therefore, you should define what you mean by it whenever you use it. But it's fine, in principle. It's better to use standard notation though, so you should stick to $=$ or $\in$. $\endgroup$ – AccidentalFourierTransform May 27 '18 at 15:08
  • 1
    $\begingroup$ What is just like in modular arithmetic? What is the modulus? It is common to write $2x^2 +3x \asymp 4 x^2 -2 x +5$. $\endgroup$ – quid May 27 '18 at 15:11
  • $\begingroup$ @quid That symbol (whose TeX shortcut I have forgotten) is often used for logarithmic equivalence in my field, I wouldn't consider it common as a substitute for Big Oh in general. $\endgroup$ – Ian May 27 '18 at 16:18
  • 1
    $\begingroup$ First of all, $2x^3+3x=O(x^2)$ does not mean that $\lim_{x \to \infty} (2x^2+3x)/x^2$ is a nonzero constant. It means that $\limsup_{x \to \infty} |2x^2+3x|/x^2$ is finite (possibly zero). Second, I've never seen anyone write $\equiv$ for this. If you want to be more precise (objecting to the use of $=$ in a non-referentially transparent and also non-symmetric manner) then you should use $\in$. $\endgroup$ – Ian May 27 '18 at 16:20
  • $\begingroup$ @Ian It is not a substitute. $ f \asymp g$ is used to express that $f$ is $O(g)$ and $g$ is $O(f)$, what is also written as Theta as you mentioned; in other words $|f/g|$ and $|g/f|$ are bounded (leaving aside subtleties when with 0 etc). This is somewhat common in analytic number theory. If the quotient tends to $1$ it would be $f \sim g$. But, yes, meaning of such symbols is not uniform over different fields. $\endgroup$ – quid May 27 '18 at 16:27
0
$\begingroup$

As long as you get used to "=" in big-oh and little-oh meaning set inclusion, you shouldn't have any problems. I still use "=" instead of the more accurate "$\in$".

Just remember that these are transitive relations (aRb and bRc implies aRc).

Note that, for positive functions, big-oh is reflexive (aRa) but not symmetric (aRb implies bRa) but little-oh is neither.

$\endgroup$
  • 2
    $\begingroup$ Big Oh is not symmetric. Big Theta is symmetric. Confusingly, people often write Big Oh when they mean (and can prove) the relevant Big Theta relation. $\endgroup$ – Ian May 27 '18 at 16:22
  • $\begingroup$ You are right - I will fix. Thanks. Upvoted. $\endgroup$ – marty cohen May 27 '18 at 16:33

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.