I have a big interval $I = [a, b]$ of size n.

I want an asymptotically minimal set of subintervals of $I$ (let's call it $S$) one can use to construct any subinterval of $I$, by concatenating at most $K$ subintervals - specifficaly I'm interested in $K = 3, K=5$ only, but general solution would be interesting too.

In other words, for any subinterval $i$ of $I$ I want to take at most $K$ (3, 5) elements of $S$ to get $i$. So if $i = [2, 28]$, one can take for example $[2, 10], [10, 20], [20, 28]$, if such subintervals exists in $S$ and $K=3$.

I've come up with solutions that are in $O(n^2)$ where $n = |I|$, but that is the same as naive approach of taking all the subintervals. I can get to about $1/K$ of that by having intervals of size $m$ to generate also the $K$ bigger intervals, but it seems it is in the spirit of the puzzle to have asymptotically better solution than $O(n^2)$, at least for $K=5$.

  • $\begingroup$ Please credit the original source of the problem. $\endgroup$
    – John L.
    Dec 18 '18 at 20:17

Let's consider the case $K = 2$. Given an interval $[1,n]$ of length $n$, we can construct the required set as follows:

  • If $n = 1$, take the entire interval.
  • Otherwise, let $m = \lfloor n/2 \rfloor$, and take the following intervals:
    1. A solution for $[1,m]$.
    2. A solution for $[m+1,n]$.
    3. All intervals of the form $[i,m]$.
    4. All intervals of the form $[m,j]$.

Denoting by $A(n)$ the number of intervals constructed in this way, we get the recurrence $$ A(n) = A(\lfloor n/2 \rfloor) + A(\lceil n/2 \rceil) + n, $$ with initial value $A(1) = 1$. The solution of this recurrence is $A(n) = \Theta(n\log n)$.

Now let us proceed to prove a matching lower bound. Let $\ell_i = 2^i-1$, and let $I$ be the maximum value such that $\ell_i \leq n/2$; note that $I = \Theta(\log n)$. For each $1 \leq i \leq I$, consider the $n/2$ intervals $[1,\ell_i],\ldots,[n/2,n/2+\ell_i-1]$ of length $\ell_i$. Each of these is the union of at most two intervals in $S$, one touching the left endpoint and one the right endpoint (possibly the same one). One of these intervals must have size at least $2^{i-1} > \ell_{i-1}$. In total, this gives a collection of $n/2$ intervals in $S$ of length between $\ell_{i-1}+1$ and $\ell_i$; each such interval is repeated at most twice (since one of its endpoints is a matching endpoint of one of the original $n/2$ intervals). This shows that $S$ must contain at least $n/4$ intervals of size between $\ell_{i-1}+1$ and $\ell_i$, and so $\Omega(nI) = \Omega(n\log n)$ overall.

Here is a better construction for $K=4$. Divide the interval $[1,n]$ into $m=n/\log n$ subintervals $I_1,\ldots,I_m$ of length $\log n$. We construct the required set as follows:

  • Apply the construction recursively inside each $I_i$.
  • Every prefix and suffix of each $I_i$, $2n$ intervals in total.
  • The $K=2$ construction applied to $[1,m]$ and then blown up to $I_1,\ldots,I_m$ by replacing each interval $[i,j]$ to $I_i,\ldots,I_j$.

Let us first show that we can cover each interval $I$ using at most 4 intervals in the set. If $I \subseteq I_i$ for some $i$, then this is clear. Otherwise, suppose that $I \subseteq I_i \cup \cdots \cup I_j$, where $i$ is maximal and $j$ is minimal. So $I$ consists of a suffix of $I_i$, all the intervals $I_{i+1},\ldots,I_{j-1}$ (if any), and a prefix of $I_j$. We can cover the middle part using 2 intervals, and the two ends using 2 more intervals, for a total of 4.

Let us denote by $B(n)$ the number of intervals used in this construction. This quantity satisfies the recurrence $$ B(n) = \frac{n}{\log n} B(\log n) + O(n). $$ Opening this up, we get $$ B(n) = O(n) + \frac{n}{\log n} O(\log n) + \frac{n}{\log n} \frac{\log n}{\log \log n} O(\log \log n) + \cdots, $$ where the hidden constant is the same for all big O’s. The number of summands is $\log^* n$ (which is the number of $\log$s you have to apply to $n$ to reduce it below some constant), and so $$ B(n) = O(n\log^* n). $$ We can repeat this construction once again, for $K=6$, to get the inverse of one level higher on the Ackermann hierarchy. Perhaps in this way we can get a set of $O(n)$ intervals for $K=\omega(1)$ growing extremely slowly (inverse Ackermann); verifying this would require a slightly more careful analysis.

  • $\begingroup$ Lovely solution and proof! I got a bit stuck trying to interpret "Each of these is covered by at most two intervals in $S$" but in the end realised the right interpretation was "For each of these intervals $X$, there is a pair of intervals $Y, Z \in S$ such that $X=YZ$". $\endgroup$ Jan 18 '19 at 16:44

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.