# Big Oh notation, some of my concerns about its definition

The formal definition of big $$O$$ notation we use is:

"We write $$f(x)=O(g(x))$$ as $$x\to x_0$$, if there exists $$A$$ such that $$|f(x)|\leq A|g(x)|$$ in the neighbourhood of $$x_0.$$"

So there are a few confusions/concerns of mine that I wanted to share:

$$1)$$ Why, in most examples I saw, they always compare $$f(x)$$ with $$x$$ to some power. I mean, could we in theory compare $$f(x)$$ to any $$g(x)$$ like $$\arctan x$$ or something less ordinary?

$$2)$$ If $$g(x)$$ is not restricted to a certain type of function, by that definition above, could we take any function $$g(x)$$ and we multiply $$|g(x)|$$ by an arbitrarily large number $$A$$ such that it is larger than $$|f(x)|$$ in some arbitrarily small domain around $$x_0$$?

• 1) Simply because it's easier to compute with power series, and their asymptotic behaviour is well known . Sometimes, you can also compare to Bertrand's series ($\sum\frac1{n^\alpha\log^\beta n}$). 2) Yes, it is valid if you can do that. Mar 8, 2020 at 18:53

However, note that some times you want more complicated functions. For instance, when multiplying together two $$n\times n$$ matrices, the naive algorithm is of the order $$n^3$$, so any decent algorithm will be $$O(n^3)$$as $$n$$ grows. There is a theoretical lower bound of $$O(n^2)$$, as there are $$2n^2$$ entries that all contribute to the result. This bound has yet to be reached, though.
However, there is active research on how close to $$O(n^2)$$ we can make it. The best result per Wikipedia right now is an algorithm of complexity $$O(n^{2.373})$$. Limiting ourselves to $$O(n^2)$$ and $$O(n^3)$$ wouldn't do.
Another example is sorting algorithms (specifically comparison sorting). The most naive algorithms have complexity on the order of $$n^2$$, and it is known that $$O(n)$$ is theoretically impossible. But many more clever algorithms run in $$O(n\log n)$$. If we limited ourselves to $$O(n^2)$$ and $$O(n)$$, we wouldn't be able to capture this.
2) The definition of $$O$$ doesn't care about constants. No matter how large.