<p>Yes!</p>

<p>Use a two-level structure as discussed at the end of Section 2 of the Dietz and Sleator paper. For the top structure, use a scapegoat tree. By using a balance factor that can be implemented in $AC^0$ (like $2$), we get the result.</p>

<p>See also <a href="http://opendatastructures.org/ods-cpp/8_2_Discussion_Exercises.html">exercise 8.12 from open data structures</a> and <a href="http://users-cs.au.dk/gerth/alcom-ft/TR/ALCOMFT-TR-01-167.ps.gz">Roura's "A new method for balancing binary search trees"</a>.</p>

CC BY-SA 3.0
2013-04-13T22:34:38.970Z
2013-04-13T22:34:38.970Z
jbapple
<p>The order maintenance problem (or "maintaining order in a list") is to support the operations:</p>

<ul>
<li><code>singleton</code>: creates a list with one item, returns a pointer to it</li>
<li><code>insertAfter</code>: given a pointer to an item, inserts a new item after it, returning a pointer to the new item</li>
<li><code>delete</code>: given a pointer to an item, removes it from its list</li>
<li><code>minPointer</code>: given two pointers to items in the same list, returns the one closer to the front of the list</li>
</ul>

<p>I am aware of three solutions to this problem that perform all operations in $O(1)$ amortized time. They all use multiplication.</p>

<ul>
<li><a href="http://dx.doi.org/10.1007/BF00289142">Athanasios K. Tsakalidis: Maintaining order in a generalized linked list</a></li>
<li><a href="http://www.cs.cmu.edu/~sleator/papers/maintaining-order.html">Dietz, P., D. Sleator, Two algorithms for maintaining order in a list</a></li>
<li><a href="http://erikdemaine.org/papers/DietzSleator_ESA2002/">Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito, “Two Simplified Algorithms for Maintaining Order in a List”</a></li>
</ul>

<p>Can order be maintained in a list in $O(1)$ amortized time without using any arithmetic operations not in $AC^0$?</p>

CC BY-SA 3.0
2014-06-09T04:50:19.723Z
Multiplication has only recently (since Pentium III) been in $AC^0$. Can we include solutions which use multiplication?
A T
CC BY-SA 3.0
2014-06-09T04:57:01.827Z
I don't think that's correct. First, I don't think multiplication is in $AC^0$. Second, I don't think particular machines, like the Pentium III you mention, have anything to do with the question of whether multiplication is in $AC^0$. Finally, as demonstrated in the question, I obviously am aware of several multiplication-based algorithms for this problem, so adding more in a new "answer" does not in any way improve things.
jbapple
CC BY-SA 3.0
2014-06-09T09:32:25.233Z
Found where I read about this; it was about Pentium 4 not III; and didn't implement multiplication instead worked around it with a new instruction from that processor: M. Thorup, ‘On AC0 Implementations of Fusion Trees and Atomic Heaps’, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA, 2003, pp. 699–707.
A T
<ds.data-structures>
Maintaining order in a list in $AC^0$ in $O(1)$ time
jbapple
# Maintaining order in a list in $AC^0$ in $O(1)$ time

(Asked by: username_0 on 2011-09-26)

The order maintenance problem (or "maintaining order in a list") is to support the operations:

* `singleton`: creates a list with one item, returns a pointer to it
* `insertAfter`: given a pointer to an item, inserts a new item after it, returning a pointer to the new item
* `delete`: given a pointer to an item, removes it from its list
* `minPointer`: given two pointers to items in the same list, returns the one closer to the front of the list

I am aware of three solutions to this problem that perform all operations in $O(1)$ amortized time. They all use multiplication.

* [Athanasios K. Tsakalidis: Maintaining order in a generalized linked list](http://dx.doi.org/10.1007/BF00289142)
* [Dietz, P., D. Sleator, Two algorithms for maintaining order in a list](http://www.cs.cmu.edu/~sleator/papers/maintaining-order.html)
* [Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito, “Two Simplified Algorithms for Maintaining Order in a List”](http://erikdemaine.org/papers/DietzSleator_ESA2002/)

Can order be maintained in a list in $O(1)$ amortized time without using any arithmetic operations not in $AC^0$?

**Tags:** ds.data-structures
> **Comments:**
> **username_1**: Multiplication has only recently (since Pentium III) been in $AC^0$. Can we include solutions which use multiplication?  
> **username_0**: I don't think that's correct. First, I don't think multiplication is in $AC^0$. Second, I don't think particular machines, like the Pentium III you mention, have anything to do with the question of whether multiplication is in $AC^0$. Finally, as demonstrated in the question, I obviously am aware of several multiplication-based algorithms for this problem, so adding more in a new "answer" does not in any way improve things.  
> **username_1**: Found where I read about this; it was about Pentium 4 not III; and didn't implement multiplication instead worked around it with a new instruction from that processor: M. Thorup, ‘On AC0 Implementations of Fusion Trees and Atomic Heaps’, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA, 2003, pp. 699–707.  

---

## 1 answers

### Answer by username_0 on 2013-04-13. Score: 6 | Accepted answer

Yes!

Use a two-level structure as discussed at the end of Section 2 of the Dietz and Sleator paper. For the top structure, use a scapegoat tree. By using a balance factor that can be implemented in $AC^0$ (like $2$), we get the result.

See also [exercise 8.12 from open data structures](http://opendatastructures.org/ods-cpp/8_2_Discussion_Exercises.html) and [Roura's "A new method for balancing binary search trees"](http://users-cs.au.dk/gerth/alcom-ft/TR/ALCOMFT-TR-01-167.ps.gz).


---

