deque vs list: performance notes

[Courageous]

> > a deque is O(n), while the cost of removing all n members
> > from a python list is O(n!).
> 
>      You sure about that "n!"? Seems more like n^2 to me.
> (Of course n^2 is big, but n! would be much worse. It's
> a theorem that n! is bigger than anything.)

Yeah, that was an error. What I was thinking when I wrote
n! was n+n-1+n-2... It's been a long time since my complexity
theory class, so I don't recall if that's identical to n^2
or not. Anyway, I knew that n! would come back to haunt me. :)-



C/