What are these asymptotics called when two functions are bounded by a fixed shift of the other?

103 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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))$.