3
$\begingroup$

When studying large numbers and extremely fast growing functions, I've noticed that the normal big-O notations are not enough to reasonably compare things. Instead, I've been using this:

$$f=\operatorname{bounded}(g)\iff\exists a<b\exists x_0\forall x>x_0(g(x+a)<f(x)<g(x+b))$$

That is, $f$ is bounded by fixed shifts of $g$. This comes in handy, especially for functions $\in\Omega(^na)$, that is, functions that grow faster than tetration, like the Ackermann function and stuff.

Is there a name for this kind of bound or similar type of bound?


One could also consider the maximum $a$ and minimum $b$ as functions of $x_0$ and then describe how close $f$ and $g$ are to one another.

$\endgroup$

1 Answer 1

1
+50
$\begingroup$

If $g$ is bijective you can say $g^{-1} \circ f = x + O(1)$.

If you're not afraid to bend notations a bit and spend a line or two putting a proper explanation for it, you may also write it like $f(x) = g(x + O(1))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.