3
$\begingroup$

The Bentley-Saxe trick allows us to go from a static decomposable problem to a problem admitting insertions, where the insertion time is off the optimal time by a factor of $\log n$.

Is this tight ? Or alternately, is there a more restricted subclass for which you can get insertion time $P(n)/n$ (amortized or worst-case) even if $P(n) = O(n\log n)$ ? Here, $P(n)$ is the time to compute the result statically.

$\endgroup$
3
$\begingroup$

Think about your question in reverse: suppose you have a dynamic data structure for some problem — does that imply that you can solve it statically, faster by a log? Why should it? And in fact it is not true.

Consider range counting in one-dimensional intervals, in a comparison model of computation. That is, the data is a set $S$ of numbers, the query is an interval $[\ell,r]$, and the answer to a query is the size of $S\cap[\ell,r]$. Statically, you can solve it in $O(\log n)$ query time by storing $S$ as a sorted array and using binary search, in preprocessing time $P(n)=\Theta(n\log n)$. Dynamically, you can still solve it in $O(\log n)$ query time by using balanced binary search trees, with insertion time $O(\log n)=O(P(n)/n)$.

$\endgroup$
  • 1
    $\begingroup$ You are right of course. But I did find a paper by Mehlhorn and Overmars arguing that the Saxe-Bentley bounds (or variants of them) are tight in general. $\endgroup$ – Suresh Venkat Apr 20 '13 at 7:13
  • 1
    $\begingroup$ @SureshVenkat: What is the name of that paper? $\endgroup$ – jbapple Apr 20 '13 at 19:33
  • 1
    $\begingroup$ mpi-sb.mpg.de/~mehlhorn/ftp/mehlhorn27.pdf (Optimal Dynamization of decomposable searching problems) $\endgroup$ – Suresh Venkat Apr 20 '13 at 22:17
  • 1
    $\begingroup$ I think the claim is that Saxe-Bentley is tight assuming a certain kind of black-box access to the static data structures. $\endgroup$ – Sasho Nikolov Apr 21 '13 at 7:34

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.