Big Oh notation, some of my concerns about its definition

Question

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$?

Answer 1

1) Because they are easy to work with, and as long as they get the job done, there isn't much need to complicate matters.

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.