<p>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.</p>

<p>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)$.</p>

CC BY-SA 3.0
2013-04-20T07:13:07.500Z
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.
Suresh Venkat
CC BY-SA 3.0
2013-04-20T19:33:20.273Z
@SureshVenkat: What is the name of that paper?
jbapple
CC BY-SA 3.0
2013-04-20T22:17:21.697Z
http://www.mpi-sb.mpg.de/~mehlhorn/ftp/mehlhorn27.pdf (Optimal Dynamization of decomposable searching problems)
Suresh Venkat
CC BY-SA 3.0
2013-04-21T07:34:59.057Z
I think the claim is that Saxe-Bentley is tight assuming a certain kind of black-box access to the static data structures.
Sasho Nikolov
CC BY-SA 3.0
2013-04-19T21:15:46.337Z
2013-04-19T21:15:46.337Z
David Eppstein
<p><a href="http://www.cs.uiuc.edu/~jeffe/teaching/datastructures/notes/01-statictodynamic.pdf" rel="nofollow">The Bentley-Saxe trick</a> 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$. </p>

<p>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. </p>

<ds.data-structures><dynamic-algorithms>
Optimal insertion times in insertion-only data structures beyond Bentley-Saxe
Suresh Venkat
# Optimal insertion times in insertion-only data structures beyond Bentley-Saxe

(Asked by: username_0 on 2013-04-19)

[The Bentley-Saxe trick](http://www.cs.uiuc.edu/~jeffe/teaching/datastructures/notes/01-statictodynamic.pdf) 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.

**Tags:** ds.data-structures, dynamic-algorithms

---

## 1 answers

### Answer by username_1 on 2013-04-19. Score: 3 | Accepted answer

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)$.

> **Comments:**
> **username_0**: 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.  
> **username_2**: @SureshVenkat: What is the name of that paper?  
> **username_0**: http://www.mpi-sb.mpg.de/~mehlhorn/ftp/mehlhorn27.pdf (Optimal Dynamization of decomposable searching problems)  
> **username_3**: I think the claim is that Saxe-Bentley is tight assuming a certain kind of black-box access to the static data structures.  

---

