Big-O notation $=$ or $\equiv$

185 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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.