time bounds for BinaryRandList (was ANN: Edison 1.2RC4)

Okasaki, C. DR EECS Christopher.Okasaki at usma.edu
Fri Jun 2 11:41:51 EDT 2006

Jim Apple wrote:
> the source for BinaryRandList at
> , I don't think the constant time bounds in the documentation are
> correct for this sequence type.

Ross Patterson replied:
> Indeed not.  If you have a sequence of exactly 2^n elements and then
> alternate between tail and cons, each operation will cost O(log n).

Yes, for this implementation, head and tail cost O(log n).  However,
using amortization, you can still count cons as O(1), using the usual
arguments to show that incrementing a binary number takes O(1)
amortized time.

-- Chris

More information about the Libraries mailing list