deque vs list: performance notes

[Russell Turpin]

Courageous wrote:
> 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. 

Arithmetically-and-all-for-doing-it-from-both-ends'ly yrs,
Russell