Recently I came across asympotic inequalities of the form $f(x) \le g(x) + O(1)$ in Li and Vitanyi’s An Introduction to Kolmogorov Complexity and Its Applications, where this notion is used to discuss bounds on the complexity of strings. In this post I give a brief definition of what this notation means and how it relates to standard asymptotic notation. Particulary, I’m only going to talk about the case of $O(1)$, but the same ideas can be extended to $O(h(x))$ for any function $h(x)$.
Standard Big O Asymptotics Link to heading
Undergraduate computer science students should be familiar with the standard $f(x) = O(g(x))$ notation, meaning:
$$ \exists C > 0, \exists x_0, \forall x > x_0, |f(x)| \le C |g(x)| $$
when we have $f(x) = g(x) + O(1)$, we interpret this as $f(x) - g(x) = O(1)$, which means that the difference between $f(x)$ and $g(x)$ is bounded by a constant. Formally, this can be written as:
$$ \exists C > 0, \exists x_0, \forall x > x_0, |f(x) - g(x)| \le C $$
Note that the absolute value is important here, this means we have both an upper and lower bound on $f(x)$ in terms of $g(x)$, specifically: $$ g(x) - C \le f(x) \le g(x) + C $$
Asymptotic Inequality Notation Link to heading
So what about $f(x) \le g(x) + O(1)$? This conveys a similar idea with a focus on only the upper bound of $f(x)$ in terms of $g(x)$. It means that there exists some constant $C$ such that for sufficiently large $x$, $f(x) \le g(x) + C$. Formally:
$$ \exists C > 0, \exists x_0, \forall x > x_0, f(x) \le g(x) + C $$
... continue reading