deque vs list: performance notes
David C. Ullrich
ullrich at math.okstate.edu
Wed May 31 17:17:47 EDT 2000
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
More information about the Python-list
mailing list