What is f(x) ≤ g(x) + O(1)? Inequalities With Asymptotics
5 days ago
- #asymptotic notation
- #Kolmogorov complexity
- #Big O
- The article discusses asymptotic inequalities of the form $f(x) \le g(x) + O(1)$, focusing on bounds in Kolmogorov complexity.
- Standard Big O notation $f(x) = O(g(x))$ is defined, indicating $f(x)$ is bounded by $C|g(x)|$ for some constant $C$ beyond a point $x_0$.
- The expression $f(x) = g(x) + O(1)$ is interpreted as $f(x) - g(x) = O(1)$, meaning the difference between $f(x)$ and $g(x)$ is bounded by a constant.
- The article explains the formal definition of $f(x) \le g(x) + O(1)$, emphasizing it only provides an upper bound, unlike the two-sided bound of standard Big O.
- It clarifies that $f(x) = g(x) + O(1)$ implies $f(x) \le g(x) + O(1)$, but the reverse is not necessarily true.