27
$\begingroup$

Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time?

  • GetElement(k): Return the $k$th element of the list.

  • InsertAfter(x,y): Insert the new element y into the list immediately after x.

  • Delete(x): Remove x from the list.

For the last two operations, you can assume that x is given as a pointer directly into the data structure; InsertElement returns the corresponding pointer for y. InsertAfter(NULL, y) inserts y at the beginning of the list.

For example, starting with an empty data structure, the following operations update the ordered list as shown below:

  • InsertAfter(NULL, a) $\implies$ [a]
  • InsertAfter(NULL, b) $\implies$ [b, a]
  • InsertAfter(b, c) $\implies$ [b, c, a]
  • InsertAfter(a, d) $\implies$ [b, c, a, d]
  • Delete(c) $\implies$ [b, a, d]

After these five updates, GetElement(2) should return d, and GetElement(3) should return an error.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ In Optimal Algorithms for List Indexing and Subset Rank (1989) I found a $\Omega{(\frac{log\ n}{log\ log\ n})}$ solution to this problem. $\endgroup$
    – A T
    Commented May 21, 2012 at 7:57
  • 2
    $\begingroup$ @Raphael: I think he means the element that would be called $A[k]$ if the data structure were an array. Arrays support the first operation in $O(1)$ time but not the second; linked lists support the second operation in $O(1)$ time but not the first. $\endgroup$
    – JeffE
    Commented May 21, 2012 at 8:51
  • 2
    $\begingroup$ Also, balanced binary trees support both operations in $O(\log n)$ time. $\endgroup$
    – JeffE
    Commented May 21, 2012 at 8:56
  • 1
    $\begingroup$ @Raphael: Edited to clarify. $\endgroup$
    – JeffE
    Commented May 21, 2012 at 9:13
  • 2
    $\begingroup$ @JeffE the dynamic array supports the first two in $O(1)$ amortized time (cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf) $\endgroup$
    – didest
    Commented May 21, 2012 at 21:11

2 Answers 2

Reset to default
36
$\begingroup$

NO.

Fredman and Saks proved that any data structure that supports these operations requires at least $\Omega(\log n/\log\log n)$ amortized time per operation. (This is reference [1] in the paper by Dietz that you mention in your first comment.) The lower bound holds in the very powerful cell probe model of computation, which only considers the number of distinct memory addresses accessed by the update and query algorithms.

Without some additional assumptions about the update and query operations, Dietz's data structure is the best possible (at least up to constant factors).

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ @AT: That bound was never "proved wrong". There are situations where it does not apply, but that is an entirely different statement! $\endgroup$
    – Raphael
    Commented May 21, 2012 at 15:22
  • 5
    $\begingroup$ @AT: The sorting lower bound was proved in a much weaker model of computation, namely binary decision trees. The bound was "proved wrong" by developing faster algorithms that cannot be described as binary decision trees. In order to prove Fredman and Saks' lower bound wrong, you'll have to design a faster algorithm that doesn't access memory. Best of luck. $\endgroup$
    – JeffE
    Commented May 21, 2012 at 17:51
  • $\begingroup$ @JeffE and Raphael; please review my other answer and confirm/deny my result when you get the chance. Thanks. $\endgroup$
    – A T
    Commented Jan 7, 2013 at 4:27
7
$\begingroup$

Looks like the $\Omega(\dfrac{\log n}{\log\log n})$ barrier has been overcome by modifying the analysis from the chronogram technique.

The new [lower] $\Omega(\log n)$ bound has been proved for similar problems in the cell-probe model [1]. From reading that article; it is my understanding that that bound applies to the list representation problem also.

[1] Patrascu, Mihai, and Erik D. Demaine. “Logarithmic Lower Bounds in the Cell-Probe Model.” SIAM J. Comput. 35, no. 4 (April 2006): 932–963. doi:10.1137/S0097539705447256.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ This lower bound holds for constant-sized words, whereas the earlier $\Omega(\log n/\log\log n)$ lower bound is for logarithmically-sized words. $\endgroup$
    – Yuval Filmus
    Commented Jan 8, 2013 at 1:00
  • $\begingroup$ Indeed. Also, can you confirm that this bound applies to the list representation problem with constant-sized words? $\endgroup$
    – A T
    Commented Jan 11, 2013 at 6:26
  • 1
    $\begingroup$ I can confirm that, because of the Dietz bound (hdl.handle.net/1802/5694) that you yourself mentioned. This makes the complexity exactly $\Theta(\log n/\log \log n)$, and therefore not $\Omega(\log n)$. $\endgroup$
    – jbapple
    Commented Mar 16, 2015 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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