deque vs list: performance notes
noone at do.not.use
Wed May 31 18:13:59 CEST 2000
> 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.
1 + 2 + .. + n = (n)(n+1)/2, which is O(n^2).
1 * 2 * .. * n = n!, as a definition.
O(n!) is much worse than O(n^2), even worse than O(2^n), but
not as bad O(n^n).
You can use integer division for (n)(n+1)/2, since (n)(n+1)
is an even number.
I wish the default implementation for lists were deques, so
that I didn't have to worry about which end of a list I add
to or remove from.
More information about the Python-list