2 Jun
2006
2 Jun
'06
11:41 a.m.
Jim Apple wrote:
the source for BinaryRandList at
http://www.eecs.tufts.edu/~rdocki01/edison/_darcs/current/edison-core/sr c/Data/Edison/Seq/BinaryRandList.hs
, 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