ocaml-batteries-team/batteries-included — Issue #192: Wrong complexity in BatDequeue
Author: sliquister
Created: 2011-12-20 11:03:06+00:00
State: open

The main operations of BatDequeue, front and rear should be constant time (and are documented as being amortized constant time) but they are not.

When you take a look at the implementation, you can see that if you build a dequeue of size n by adding all the elements at the front (with cons), and then
- call rear on the queue
- call front on the remaining queue
- call rear on the remaing queue etc.
then all the calls to rear and front take linear time in the current size of the queue, there is no amortization.

This should be solved by changing front so that when the front list is empty, it puts only half of the rear list in front, instead of putting the whole rear list (and the symmetric change in rear).

Even with this, the complexity would be amortized constant time only for 'single threaded' usage of the structure. You would need some memoization as in described in Okasaki's Purely Functional Datastructures to have an amortized constant time complexity in a persistent setting.
If the current behaviour is the desired one, I think the documentation should say so.