<p>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.</p>

<p>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 &amp;\ge c a(n) \\
f(b)-f(a) &amp;= \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.</p>

CC BY-SA 3.0
2014-02-15T00:37:22.063Z
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
CC BY-SA 3.0
2014-02-15T14:48:01.773Z
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
CC BY-SA 3.0
2014-02-15T19:39:23.443Z
This might be a good place to look: http://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
CC BY-SA 3.0
2014-02-18T22:36:10.373Z
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
CC BY-SA 3.0
2014-02-15T00:02:11.460Z
2014-02-18T22:35:14.247Z
2014-02-18T22:35:14.247Z
Geoffrey Irving
<p>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$?</p>

<p>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.</p>

CC BY-SA 3.0
2014-02-14T19:28:03.903Z
If you need a motivating example try this, https://oeis.org/A011371 . The $a(n)$ term is near $log_{2}(n)$.
Chad Brewbaker
CC BY-SA 3.0
2014-02-14T23:13:43.147Z
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
CC BY-SA 3.0
2014-02-14T23:41:53.773Z
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
<time-complexity><asymptotics>
Complexity of generically inverting a class of near linear monotonic functions
Chad Brewbaker
# Complexity of generically inverting a class of near linear monotonic functions

(Asked by: username_0 on 2014-02-14)

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.

**Tags:** time-complexity, asymptotics

> **Comments:**
> **username_0**: If you need a motivating example try this, https://oeis.org/A011371 . The $a(n)$ term is near $log_{2}(n)$.  
> **username_1**: Can we assume that an upper bound on $n$ is known?  I.e., given $m$, we know $n$ s.t. $f(n) \ge m$?  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2014-02-15. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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))$  
> **username_1**: This might be a good place to look: http://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.  
> **username_1**: 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.  

---

