4 ms·
This talks about the O(n)-ness of length, but I don't see the rationale for the O(n)-ness of pop. Maybe I'm missing something?
by rtpg 12y ago
This talks about the O(n)-ness of length, but I don't see the rationale for the O(n)-ness of pop. Maybe I'm missing something?
- felixgallo 12y agoYou fell victim to the confusion in the original post and this thread between what the original poster describes as popping, and what they were apparently actually doing (which involved taking the length, which is O(N) for the reasons explained here and in the documentation). erlang's queue's pop ("out") is amortized O(1), worst case O(N) just like every other immutable double headed queue. Here's the source code: https://github.com/erlang/otp/blob/172e812c491680fbb175f56f7604d4098cdc9de4/lib/stdlib/src/queue.erl#L137 https://github.com/erlang/otp/blob/172e812c491680fbb175f56f7...