Maximum amount of iterations to get to an empty list from repeatedly taking the smallest complement of a list

Question

I was trying to solve Iterative Smallest Complement on the Code Golf website, and thought of an interesting question.

A basic run down of what the smallest complement of a list is:

... B is a complement of A if:

• B has all of the integers between the minimum and maximum of A which are missing from A, and
• B has none of the integers present in A

So basically, you make the list $[\min(A)\ldots\max(A)]\backslash A$, where $\backslash$ represents set difference.

Now given a list of non-repeating numbers $A$, repeatedly find the smallest complement until you obtain the empty set, and record how many iterations it took. Iterations include the initial list $A$ and the empty set: $\{\}$.

For example, given $A=[1,3,4,5,8]$, the iterations are as follows:

1. $[1,3,4,5,8]$
2. $[2,6,7]$
3. $[3,4,5]$
4. $[]$

So, $4$ iterations when $A=[1,3,4,5,8]$.

---

Now I was wondering: For any given list $L$ which includes no repeating numbers, what is the highest amount of iterations possible? I'm looking for some kind of expression in terms of $L$ (like its length, or maximum value, etc.).

I'm also wondering if there is some kind of algorithm which can generate a list with the most amount of iterations.

Answer 1

Line up the integers from $\min(A)$ to $\max(A)$ (inclusive) in order and color everyone $\in A$ red and everyone else blue. E.g. $\color{red}{1} \color{blue}{2} \color{red}{3 4 5} \color{blue}{6 7} \color{red}{8}$.

Define a block as a maximal-sized sequence of consecutive same colored integers. E.g. the above example has $5$ blocks. The number of transitions would be $\frac{B+1}{2}$ where $B$ is the number of blocks, since each transition (except the last) removes the outermost two (same colored) blocks and then flip each remaining block's color, and the last transition removes the last block. Since you count the original as an iteration also, the answer is $1 + \frac{B+1}{2}$.

It is therefore clear that for any given $\min(A), \max(A)$ the number of iterations is maximized if you maximize the number of blocks, i.e. include every other number in $A$ (subject to parity).