deque vs list: performance notes

[David C. Ullrich]

Courageous <jkraska1 at san.rr.com> wrote in article
<393530D7.D495D3F9 at san.rr.com>...
> 
> > > 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.

	Forget what they taught you in that class and ask yourself
how big _is_ it? On the one hand all the terms are less than
or equal to n and there are n terms, so the sum is less than n^2.
On the other hand half the terms are larger than n/2, and that's
n/2 terms, so the sum is larger than n^2/4. So it's "exactly"
O(n^2).

> Anyway, I knew that n! would come back to haunt me. :)-

	Boo.

> C/
> 

DU