Minimum number of $|\cdot|$ operations necessary to express $\max$

Question

For two variables, their maximum $\max\{x_1,x_2\}$ can be expressed using one $|\cdot|$ operation: $$ \max\{x_1,x_2\} = \frac12(x_1+x_2+|x_1-x_2|). $$ For $3$ variables, it seems fairly clear that three $|\cdot|$ operations are necessary, though I can only demonstrate sufficiency: $$ \max\{x_1,x_2,x_3\} = \frac14\left[ 2x_1+x_2+x_3+|x_2-x_3|+2\left|x_1-\frac12(x_2+x_3+|x_2-x_3|)\right| \right] . $$ For $5$ variables, it has been claimed here https://twitter.com/ereliuer_eteer/status/1669081421007454209 that the minimum number of $|\cdot|$ operations is 54, though I have verified neither sufficiency nor necessity.

Question: How many $|\cdot|$ operations are necessary for $n$ variables? To be explicit about the rules, in addition to $|\cdot|$, the 4 arithmetic operations are allowed.

Update. That twitter post I linked is actually computing the median, not the max of 5 variables. So the analogous question for abs-operation complexity, but now for the median, is quite natural.

Answer 1

Let $f(k)$ be the minimum number of $|\cdot|$ operations to express the maximum of $2^k$ variables. Using the identities $$\max\{x_1,x_2\} = (x_1+x_2+|x_1-x_2|)/2,$$ $$\max\{x_1,\ldots,x_{2^{k+1}}\} = \max\{\max\{x_1,\ldots,x_{2^k}\},\max\{x_{2^k+1},\ldots,x_{2^{k+1}}\}\},$$ it is clear that $f(1)=1$ and $f(k+1)\leq 4f(k)+1$. Hence it follows by induction that $$f(k)\leq (4^k-1)/3.$$ Now let us consider the case of $n$ variables. If $2^{k-1}<n\leq 2^k$, then the minimal number of corresponding $|\cdot|$ operations is less than $4^k/3$, which is less than $(4/3)n^2$.

Added. In fact that minimal number of $|\cdot|$ operations is less than $(3/8)n^2$. For details, see AspiringMat's response and the comments below it.

Answer 2

This is just a tighter analysis of the analysis from @GH from MO.

Let $f(n)$ be the minimum number of $|\cdot|$ operations to compute $\max(x_1, \ldots, x_n)$. Then $f(1)=0$ and for $n\geq 1$:

$$f(n)\leq 1+2\min_{1\leq j < n}\left( f(j)+f(n-j)\right)$$

Generating the first few values, we get for $n\geq 2$: $1, 3, 5, 9, 13, 17, \ldots$ which plugging into OEIS give this sequence (Shifted by 2). Plugging in, we get

$$f(n) \leq n 2^{\lfloor \log_2(n) \rfloor } - \frac{2\cdot 4^{\lfloor \log_2(n) \rfloor} + 1}{3}$$

In the notes, it says that this is the solution to the recurrence $$a(n)=1+2a(\lfloor n/2 \rfloor)+2a(\lceil n/2 \rceil) $$ which suggests that the minimization above happens precisely at $j=\lfloor n/2 \rfloor$.

The upper bound behaves like $1/3 n^2$. Comparing the upper bound above and $4/3 n^2$, we get:

One interesting note is that if we consider the DP

$$f(n)\leq \min_{i,j | 0\leq i+j <n }3+2f(i)+4f(j)+4f(n-i-j)$$

Which uses the second identity in OP's answer ($x_1$ appears twice, and $x_2, x_3$ appear 4 times, with $3$ extra $|\cdot|$), then it seems to be minimized at precisely the same minima as the 2D case. It would be interesting if there are alternative expressions for $n=3$ that use less variables which can be used to get better bounds.