4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ If you need a motivating example try this, oeis.org/A011371 . The $a(n)$ term is near $log_{2}(n)$. $\endgroup$ Feb 14, 2014 at 19:28
  • $\begingroup$ Can we assume that an upper bound on $n$ is known? I.e., given $m$, we know $n$ s.t. $f(n) \ge m$? $\endgroup$ Feb 14, 2014 at 23:13
  • $\begingroup$ 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. $\endgroup$ Feb 14, 2014 at 23:41

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Feb 15, 2014 at 0:37
  • $\begingroup$ 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))$ $\endgroup$ Feb 15, 2014 at 14:48
  • $\begingroup$ 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. $\endgroup$ Feb 15, 2014 at 19:39
  • $\begingroup$ 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. $\endgroup$ Feb 18, 2014 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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