1
$\begingroup$

Given any set of real scalar values $V=\{v_i | 1 \leq i \leq n\}$ and a distinct value $v_p$ define c:-

$ c= \sum_{i=1}^n |v_i-v_p| $

What is the easiest way to determine $v_p$ such that $c$ is minimised?

One approach would be an iterative binary search for $v_p$ between $\min(V)$ and $\max(V)$ - can this be improved upon?

2 Answers 2

3

The median of the $v_i$ minimizes this function, so you should sort the $v_i$ and pick the middle value, which takes $O(n\log n)$ time.

If $n$ is even, pick any value between the middle two elements (it is easy to see that changing $v_p \rightarrow v_p + \delta v_p$ doesn't change $c$ unless $v_p$ crosses one of the $v_i$.)

Edit:

A binary search would find an optimal value in $O(\log n)$ function evaluations, each of which executes in $O(n)$ time, for a total running time of $O(n\log n)$.

If you follow my advice and sort the $v_i$ to find the median, it will take $O(n\log n)$ comparisons on average. However, you can be smarter: using a selection algorithm it is possible to compute the sample median in $O(n)$ time, and this is a lower bound on the complexity.

0

Plot $n$, say: $9$, arbitrary points $v_i$ on a horizontal $v$-axis and mark in red a trial point $x$ in the midst between these. Now check what happens to the quantity $c(x):=\sum_{i=1}^n |v_i-x|$ when you move $x$ slightly to the left or to the right. In the end you will see where $x$ must lie to make $c(x)$ minimal. (The solution may be non-unique, as, e.g., in the case $n=2$.)