# Complexity of generically inverting a class of near linear monotonic functions

Given a monotonic increasing function $f(\mathbb{N}) \rightarrow \mathbb{N}$ and a slack function $a(\mathbb{N})\rightarrow \mathbb{N}$, where $f(n) = n \pm O(a(n))$; how many calls to $f$ do we need to brute force $f^{-1}$ as a function of $a$ and $n$?

This problem comes up regularly when you have a near linear monotonic increasing sequence on OEIS which you have a good complexity algorithm to compute it, and need a generic algorithm to get an upper bound on the complexity of computing the inverse.

• If you need a motivating example try this, oeis.org/A011371 . The $a(n)$ term is near $log_{2}(n)$. – Chad Brewbaker Feb 14 '14 at 19:28
• Can we assume that an upper bound on $n$ is known? I.e., given $m$, we know $n$ s.t. $f(n) \ge m$? – Geoffrey Irving Feb 14 '14 at 23:13
• Never mind, an upper bound is easy to arrive at based on $a(n)$, I was somehow thinking one would need the constant in advance. – Geoffrey Irving Feb 14 '14 at 23:41

A simple variant of binary search takes $O(\log a(n))$ time assuming $a(n) = O(n)$ is monotonic. To compute $f^{-1}(n)$, find $k$ s.t. $$f(n-2^k) \le n \le f(n+2^k)$$ by trying $k = 0, 1, 2, \ldots$ until the bound holds. This takes $O(\log a(n))$ steps and produces a window of size $O(a(n))$ which can be finished off with binary search.
Unfortunately, this is the best you can do without a stronger condition on $f(n)$. Proof sketch: assume that after $O(1)$ queries we've reduced to an interval $[a,b]$ s.t. \begin{aligned} b-a &\ge c a(n) \\ f(b)-f(a) &= \Theta(a(n)) \end{aligned} Then $f(n)$ within $[a,b]$ is an arbitrary monotonic function subject to the end constraints, and we can adversarily choose $f$ to make $\Theta(\log a(n))$ optimal.
• After writing this, it occurs to me that it is almost certainly not optimal if $f(n)-n$ is a "nice" function. Interpolation search can probably often do better. – Geoffrey Irving Feb 15 '14 at 0:37
• Yeah I was looking for something that could beat brute forcing it with binary search. I didn't know if there was a result out there like an interpolation. I also was playing around with looking at the error of the fixed point $f_{approx}^{-1}(f(x))$ – Chad Brewbaker Feb 15 '14 at 14:48
• This might be a good place to look: link.springer.com/chapter/10.1007%2F3-540-56939-1_58. They claim $O(\log^* n)$ interpolation search on sufficiently smooth distributions. I haven't read it in detail, though, so I'm not sure it applies. – Geoffrey Irving Feb 15 '14 at 19:39
• I added the sketch that this is (unfortunately) optimal given the problem as specified. In practice you should be able to do better, more you'll need more knowledge of $f$ to prove anything. – Geoffrey Irving Feb 18 '14 at 22:36