<p>A computer scientist oriented toward applications gave me the following problem:</p>

<blockquote>
  <p>Given a positive integer $n&gt;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]}$.</p>
</blockquote>

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

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

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

CC BY-SA 3.0
2015-01-06T18:54:56.240Z
See [this problem](http://cs.stackexchange.com/questions/18211/maxima-of-diagonals-in-a-column-wise-and-row-wise-sorted-matrix). 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)
Chao Xu
CC BY-SA 3.0
2015-01-12T09:16:04.760Z
Thanks, I will forward the reference to my colleague in case his application matches this problem.
J.y B.y
<ds.algorithms><time-complexity>
Is the problem "Binary Sorted Min Sum" already known under an other name?
J.y B.y
# Is the problem "Binary Sorted Min Sum" already known under an other name?

(Asked by: username_0 on 2015-01-06)

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?

**Tags:** ds.algorithms, time-complexity
> **Comments:**
> **username_1**: See [this problem](http://cs.stackexchange.com/questions/18211/maxima-of-diagonals-in-a-column-wise-and-row-wise-sorted-matrix). 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)  
> **username_0**: Thanks, I will forward the reference to my colleague in case his application matches this problem.  

---

## 0 answers

