4
$\begingroup$

Given an ordered sequence of $n$ elements, you have to choose a family $A$ of subsets of consecutive elements, such that each subset of consecutive elements (not necessairly in $A$) can be represented as a disjoint union of at most $k$ elements of $A$. Let $A$ be the minimal set with this property, define the function $f(n, k):=|A|$. Now I am really interested in how this function behaves. Notice that $A$ actually describes a data structure which is capable of answering most kinds of interval queries (the sequence of elements have to be elements of a monoid) in $k$ "operations". I've discussed it with some of my colleagues and we have noticed the following:

Obviously $f(n, 1) = {n \choose2}$.

Now more interestingly, $f(n, 2) = O(n \; log(n))$, and the structure of $|A|$ vaguely resembles the standard implementation of a sparse table.

Some also interesting upper bounds are $f(n, log(log(n))) = O(n \; log(log(n)))$, you can build a tree which resembles the van Emde Boas data structure.

And for $f(n, 2log(n) - 2)$ = $O(n)$ you can use the segment tree data structure. Asymptotically, $f(n, O(log(n))) = O(n)$, this is tight.

Now, I am interested in whether anyone has seen something resembling this function anywhere before? Seems like many data structures can be viewed of as optimal constructions of $A$ for different values of $k$? It would be really helpful if someone could just point me to a reference.

$\endgroup$

1 Answer 1

5
$\begingroup$

This question is answered by Alon and Schieber [1]. For a constant $k \geq 2$, the asymptotic bound is $f(n,k) = \Theta(n \lambda(k,n))$ where $\lambda(k,\cdot)$ is a certain slowly growing function. Concrete values are:

$ \begin{equation} f(n,2) = \Theta(n \log n) \\ f(n,3) = \Theta(n \log \log n) \\ f(n,4) = \Theta(n \log^\ast n) \end{equation} $

The upper bound is proven by a simple recursive algorithm.

For non-constant $k$, it is proven that $f(n,O(\alpha(n))) = \Theta(n)$ where $\alpha(n)$ is the inverse Ackermann function. This is best possible for the linear number of subsets.

  • [1] Alon, Noga, and Baruch Schieber. “Optimal Preprocessing for Answering On-Line Product Queries,” 1987.
$\endgroup$

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.