2
$\begingroup$

A computer scientist oriented toward applications gave me the following problem:

Given a positive integer $n>0$, an increasing function function $f$ and a decreasing function $g$, both defined on $[1..n]$, compute the minimal index $i\in[1..n]$ such than $f(i)+g(i)$ is minimal among values $\{f(j)+g(j)\}_{j\in[1..n]}$.

I named this problem "Binary Sorted Min Sum" for lack of a better name. The computational complexity of this problem in the worst case over instances of size $n$ is clearly $2n$ evaluations, $n-1$ comparisons, and $n$ additions, all within $O(n)$. A linear number of instances of this problem occur in the core of my colleague's solution, which complexity he analyzes as $O(n^2)$.

Inspired by the fact that many instances of this problem can be solved in sublinear time (e.g. when $f$ is increasing much faster than $g$ is decreasing, one can certify that the minimum is at index $1$ in one single comparison, 4 accesses and 2 sums), I got some interesting adaptive results, showing tight bounds within $O(\delta\lg(n/\delta)$ for some parameter $\delta\in[1..n]$ measuring the difficulty of the instance, implying both the $\Theta(n)$ bound in the worst case and the $\Theta(\lg n)$ bound in easy instances: it is actually quite similar (but not reducible, it seems) to the "Binary Sorted Intersection" problem which I studied previously.

A quick search on "Binary Sorted Min Sum" did not yield anything meaningful, yet the problem is quite simple, so I am wondering if someone introduced it before under another name?

$\endgroup$
  • $\begingroup$ See this problem. It's not the exact same problem(you want the minimum over the entire matrix instead of every diagonal), but there might be some connections. (especially your colleague is looking at a linear number of instances) $\endgroup$ – Chao Xu Jan 6 '15 at 18:54
  • $\begingroup$ Thanks, I will forward the reference to my colleague in case his application matches this problem. $\endgroup$ – Jeremy Jan 12 '15 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.