1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Bernard
    Mar 8, 2020 at 18:53

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .