<p>The answer to any of your questions depends upon the model of computation. For instance, on many machines, multiplying integers is more expensive than adding them. Some models reflect this, while some do not.</p>

<p>For an answer to your question about ordered sets of integers, Andersson and Thorup discuss an asymptotically optimal solution to maintaining a dynamic ordered set of integers in the RAM model in polynomial space in their paper <a href="http://user.it.uu.se/~arnea/ps/expTr.pdf">"Dynamic ordered sets with exponential search trees"</a>. The bound they achieve is $O(\sqrt{\log n/ \log \log n})$. The paper the cite for the lower bound is Beame and Fich's <a href="http://www.cs.washington.edu/homes/beame/papers/predecessor.ps">"Optimal Bounds for the Predecessor Problem and Related Problems"</a>.</p>

CC BY-SA 2.5
2011-03-17T19:41:13.390Z
Nice. But it seems you've overstated the result in the Andersson and Thorup paper. It applies only to linear space structures, not all polynomial space structures.
Shaun Harker
CC BY-SA 2.5
2011-03-18T02:09:40.993Z
Andersson and Thorup cite Beame and Fich for the polynomial space: "The lower bound follows from a result of Beame and Fich. It shows that even if we
just want to support insert and predecessor operations in polynomial space, one of these two operations have a worst-case bound of Ω(sqrt(log n/log log n)), matching our common upper bound. We note that one can find better bounds and trade-offs for some of the individual
operations. Indeed, we will support min, max, predecessor, successor, and delete operations
in constant time, and only do insert and search in Θ(sqrt(log n/log log n)) time."
jbapple
CC BY-SA 2.5
2011-03-18T04:25:57.557Z
I see, the linear space comes in to advertise the _upper bound_, but Corollary 3.10 of Beame and Fich gives the poly-space _lower bound_, as you stated and I foolishly contradicted. It also occurs to me that one might want to advertise worst-case times for upper bounds while advertising amortized times for lower bounds. The Andersson and Thorup paper indeed cites (page 5) Beame and Fich for an amortized lower (and upper) bound. But Corollary 3.10 only seems to give the lower bound for worst-case. Perhaps someone could give me a hint on that as well?
Shaun Harker
CC BY-SA 2.5
2011-03-17T07:37:58.763Z
2011-03-17T07:37:58.763Z
jbapple
<p>In extension to what you mention to your question, one classic example is using the fact that integers cannot be sorted using comparisons faster than $O(n \log n)$ in order to prove the non-existence of superstructures.</p>

<p>Furthermore, it is not unusual to use information theory arguments (e.g. Kolmogorov complexity) in order to prove lower bounds for data structures.</p>

CC BY-SA 2.5
2011-03-16T06:39:27.047Z
2011-03-16T06:39:27.047Z
chazisop
<p>There is a <a href="http://people.csail.mit.edu/mip/papers/unions/talk.pdf" rel="nofollow noreferrer">really nice talk</a> on the dynamic lower bounds on graphs by Mihai Pătraşcu. In summary (on p.20 of the slides), we have the lower bounds in terms of query time $t_q$ and update time $t_u$ (insert an edge):</p>

<p><img src="https://i.sstatic.net/jxeme.jpg" alt="enter image description here"></p>

<p>See the <a href="http://people.csail.mit.edu/mip/papers/unions/paper.pdf" rel="nofollow noreferrer">paper</a> for details. <a href="http://people.csail.mit.edu/mip/papers/index.html" rel="nofollow noreferrer">Some other papers</a> by Mihai are relevant and nice, too.</p>

<p>UPDATE: I found that his PhD thesis "<a href="http://people.csail.mit.edu/mip/docs/thesis-phd/phd.pdf" rel="nofollow noreferrer">Lower Bound Techniques for Data Structures</a>" providing lower bounds for many central data-structure problems using the techniques he developed. It certainly worths a read.</p>

CC BY-SA 2.5
2011-03-18T05:20:24.407Z
That thesis is wonderful, thank you very much for sharing the link.
Shaun Harker
CC BY-SA 2.5
2011-03-16T02:46:32.990Z
2011-03-17T07:54:07.947Z
2011-03-17T07:54:07.947Z
Hsien-Chih Chang 張顯之
<p>Are results known which rule out the existence of "too-good-to-be-true" data structures? </p>

<p>For example: can one add $Split$ and $Join$ functionality to an order maintenance data structure (see <a href="http://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf">Dietz and Sleator STOC '87</a>) and still obtain $\mathcal{O}(1)$ time operations? </p>

<p>Or: can one implement an ordered set with integer keys and $\mathcal{O}(1)$ time operations? Of course this is at least as hard as discovering a linear time algorithm for sorting integers.</p>

<p>Has the answer been proven to be <em>no</em> for either of these questions? Are lower bound results known for any natural data structure? </p>

CC BY-SA 2.5
2011-03-16T11:55:32.833Z
Things change if we are able to add limitations to the problem space. For example, if we have a limited set of keys and enough memory, we may sort them in linear time using a bit vector.
jetru
CC BY-SA 2.5
2011-03-17T07:15:54.017Z
I think the reason you're not getting too many answers to this question is that there are just so many possibilities. Many, many data structures have known lower bounds, and it's hard not to just stumble over them. A Google search for "data structure" "lower bound" includes, for me, 5 papers that have yet to be mentioned in this thread. I think you would have more success getting your question answered if you restricted it, perhaps by removing the part about "natural data structure[s]" and just asking about list maintenance or integer ordered sets (but not both in one question).
jbapple
CC BY-SA 2.5
2011-03-17T07:39:25.860Z
I omitted that the 5 papers I found in the Google search were on just the first page of the search results.
jbapple
CC BY-SA 2.5
2011-03-17T16:29:17.033Z
@jbapple: You are right! I think that the clicks from people in this community trying to help me with my question have pushed the good results to the top of the list. (For example, THIS page is now on the list!) I don't recall it being useful when I first did the search, or I likely would have restricted the question as you suggest. (Or I was a big dummy, that's possible too. :) )
Shaun Harker
<ds.data-structures><big-list><lower-bounds><time-complexity>
Lower Bounds for Data Structures
Shaun Harker
# Lower Bounds for Data Structures

(Asked by: username_0 on 2011-03-16)

Are results known which rule out the existence of "too-good-to-be-true" data structures?

For example: can one add $Split$ and $Join$ functionality to an order maintenance data structure (see [Dietz and Sleator STOC '87](http://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf)) and still obtain $\mathcal{O}(1)$ time operations?

Or: can one implement an ordered set with integer keys and $\mathcal{O}(1)$ time operations? Of course this is at least as hard as discovering a linear time algorithm for sorting integers.

Has the answer been proven to be *no* for either of these questions? Are lower bound results known for any natural data structure?

**Tags:** ds.data-structures, big-list, lower-bounds, time-complexity

> **Comments:**
> **username_1**: Things change if we are able to add limitations to the problem space. For example, if we have a limited set of keys and enough memory, we may sort them in linear time using a bit vector.  
> **username_2**: I think the reason you're not getting too many answers to this question is that there are just so many possibilities. Many, many data structures have known lower bounds, and it's hard not to just stumble over them. A Google search for "data structure" "lower bound" includes, for me, 5 papers that have yet to be mentioned in this thread. I think you would have more success getting your question answered if you restricted it, perhaps by removing the part about "natural data structure[s]" and just asking about list maintenance or integer ordered sets (but not both in one question).  
> **username_2**: I omitted that the 5 papers I found in the Google search were on just the first page of the search results.  
> **username_0**: @username_2: You are right! I think that the clicks from people in this community trying to help me with my question have pushed the good results to the top of the list. (For example, THIS page is now on the list!) I don't recall it being useful when I first did the search, or I likely would have restricted the question as you suggest. (Or I was a big dummy, that's possible too. :) )  

---

## 3 answers

### Answer by username_4 on 2011-03-16. Score: 19 | Accepted answer

There is a [really nice talk](http://people.csail.mit.edu/mip/papers/unions/talk.pdf) on the dynamic lower bounds on graphs by Mihai Pătraşcu. In summary (on p.20 of the slides), we have the lower bounds in terms of query time $t\_q$ and update time $t\_u$ (insert an edge):

![enter image description here](https://i.sstatic.net/jxeme.jpg)

See the [paper](http://people.csail.mit.edu/mip/papers/unions/paper.pdf) for details. [Some other papers](http://people.csail.mit.edu/mip/papers/index.html) by Mihai are relevant and nice, too.

UPDATE: I found that his PhD thesis "[Lower Bound Techniques for Data Structures](http://people.csail.mit.edu/mip/docs/thesis-phd/phd.pdf)" providing lower bounds for many central data-structure problems using the techniques he developed. It certainly worths a read.

> **Comments:**
> **username_0**: That thesis is wonderful, thank you very much for sharing the link.  

---

### Answer by username_2 on 2011-03-17. Score: 6

The answer to any of your questions depends upon the model of computation. For instance, on many machines, multiplying integers is more expensive than adding them. Some models reflect this, while some do not.

For an answer to your question about ordered sets of integers, Andersson and Thorup discuss an asymptotically optimal solution to maintaining a dynamic ordered set of integers in the RAM model in polynomial space in their paper ["Dynamic ordered sets with exponential search trees"](http://user.it.uu.se/~arnea/ps/expTr.pdf). The bound they achieve is $O(\sqrt{\log n/ \log \log n})$. The paper the cite for the lower bound is Beame and Fich's ["Optimal Bounds for the Predecessor Problem and Related Problems"](http://www.cs.washington.edu/homes/beame/papers/predecessor.ps).

> **Comments:**
> **username_0**: Nice. But it seems you've overstated the result in the Andersson and Thorup paper. It applies only to linear space structures, not all polynomial space structures.  
> **username_2**: Andersson and Thorup cite Beame and Fich for the polynomial space: "The lower bound follows from a result of Beame and Fich. It shows that even if we just want to support insert and predecessor operations in polynomial space, one of these two operations have a worst-case bound of Ω(sqrt(log n/log log n)), matching our common upper bound. We note that one can find better bounds and trade-offs for some of the individual operations. Indeed, we will support min, max, predecessor, successor, and delete operations in constant time, and only do insert and search in Θ(sqrt(log n/log log n)) time."  
> **username_0**: I see, the linear space comes in to advertise the _upper bound_, but Corollary 3.10 of Beame and Fich gives the poly-space _lower bound_, as you stated and I foolishly contradicted. It also occurs to me that one might want to advertise worst-case times for upper bounds while advertising amortized times for lower bounds. The Andersson and Thorup paper indeed cites (page 5) Beame and Fich for an amortized lower (and upper) bound. But Corollary 3.10 only seems to give the lower bound for worst-case. Perhaps someone could give me a hint on that as well?  

---

### Answer by username_3 on 2011-03-16. Score: 2

In extension to what you mention to your question, one classic example is using the fact that integers cannot be sorted using comparisons faster than $O(n \log n)$ in order to prove the non-existence of superstructures.

Furthermore, it is not unusual to use information theory arguments (e.g. Kolmogorov complexity) in order to prove lower bounds for data structures.


---

