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$
  • $\begingroup$ If you need a motivating example try this, oeis.org/A011371 . The $a(n)$ term is near $log_{2}(n)$. $\endgroup$ – Chad Brewbaker Feb 14 '14 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$ – Geoffrey Irving Feb 14 '14 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$ – Geoffrey Irving Feb 14 '14 at 23:41
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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Geoffrey Irving Feb 15 '14 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$ – Chad Brewbaker Feb 15 '14 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$ – Geoffrey Irving Feb 15 '14 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$ – Geoffrey Irving Feb 18 '14 at 22:36

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.